순회공연

2033년, 시우는 10년의 고행 끝에 양손으로 서로 다른 도형을 동시에 그리는 달인이 되었다. 시우는 수련 10주년을 기념해 $Q$개의 장소에서 순회공연을 하려고 한다. 공연마다 차별성을 주기 위해 길이 $N$의 수열 $A$를 준비하고, 각 공연에서 주어진 구간 $[l, r]$ 안의 두 인덱스 $i$, $j$를 $l \le i < j \le r$을 만족하도록 고른다. 공연은 다음과 같이 진행한다.

• 왼손으로는 완성하는 데 $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$을 출력한다.