30965번 - 순회공연

문제

2033년, 시우는 10년의 고행 끝에 양손으로 동시에 서로 다른 도형 그리기의 달인이 되었다. 시우는 수련 10주년을 기념해 $Q$개의 장소로 순회공연을 돌려고 한다. 차별성을 주기 위하여, 시우는 길이 $N$의 수열 $A$를 두고 각 공연마다 정해진 구간 $[l, r]$에서 $l \le i < j \le r$인 $i,ドル $j$를 골라 다음처럼 공연을 진행한다.

• 왼손으로는 완성하는 데에 $a$초가 걸리는 원을 반복해 그린다.
• 오른손으로는 처음에 1ドル$초간 손인사를 한 뒤 완성에 $A_i \times A_j$초가 걸리는 삼각형을 반복해 그린다.
• 완성과 반복 사이에는 조금의 멈춤도 없으며, 공연은 두 도형이 정확히 동일한 시점에 완성되는 순간 종료된다.

삼각형을 그리는 것은 매우 힘들기 때문에, 시우는 최대한 적은 개수의 삼각형을 그리려고 한다. 단, 삼각형을 하나도 그리지 않고 공연을 마치는 것은 불가능하다.

입력

첫 번째 줄에 정수 $N, Q, a$가 차례대로 주어진다. $(1 \le N, Q \le 10^5;$ 1ドル \le a \le 30)$

두 번째 줄에 수열 $A$를 이루는 정수 $N$개가 순서대로 공백으로 구분되어 주어진다. $(1 \le A_i \le 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄마다 두 정수 $l, r$이 공백으로 구분되어 주어진다. $(1 \le l < r \le N)$

출력

$Q$개의 줄에 걸쳐 각 공연에서 삼각형을 그리는 횟수의 최솟값을 출력한다. 단, 어떤 방법으로도 공연을 유한한 시간 내에 마무리할 수 없다면 $-1$을 출력한다.

제한

힌트