Touring Show

In 2033, Siu became a master of drawing two different shapes at the same time with both hands, after ten years of training. To celebrate the tenth anniversary of his training, Siu plans a tour with $Q$ venues. To make each show different, he takes a sequence $A$ of length $N$, and for each show he picks two indices $i$ and $j$ with $l \le i < j \le r$ from the given interval $[l, r]$. The show goes as follows.

• The left hand repeatedly draws a circle that takes $a$ seconds to complete.
• The right hand first waves for 1 second, then repeatedly draws a triangle that takes $A_i \times A_j$ seconds to complete.
• There is no pause between completing a shape and starting the next one. The show ends at the moment both shapes complete at exactly the same time.

Drawing triangles is very tiring, so Siu wants to draw as few triangles as possible. However, it is impossible to finish the show without drawing any triangle.

The first line contains integers $N$, $Q$, and $a$ in that order. ($1 \le N, Q \le 10^5$, $1 \le a \le 30$)

The second line contains the $N$ integers of sequence $A$, separated by spaces, in order. ($1 \le A_i \le 10^9$)

From the third line, each of the next $Q$ lines contains two integers $l$ and $r$, separated by a space. ($1 \le l < r \le N$)

For each show, print on its own line the minimum number of triangles drawn. If the show cannot be finished in finite time by any method, print $-1$.