SOLVE

LATER

Mojtaba's Array and Arpa's Queries

/

Mojtba has an array $$a$$ with $$n$$ elements and an integer $$k$$. Arpa has $$q$$ query in type $$[L, R]$$, for $$i$$-th query print the length of the shortest segment $$[x, y] \in [L_i, R_i]$$, such that \(k | \prod_{j=x}^y a_j\).

**Input Format**

The first line of input will contain three integers, $$n, k, q$$ ($$1 \le n, q \le 5 \cdot 10^5$$, $$1 \le k \le 10^9$$).

Next line will contain $$n$$ integers \(a_{1}, a_{2}, a_{3},...,a_{n}\) - integers of the array $$a$$ ($$1 \le a_i \le 10^9$$).

In $$i$$-th line of the next $$q$$ lines, two integers given, $$L_i, R_i$$ ($$1 \le L_i \le R_i \le n$$).

**Output Format**

For each query print the length of the shortest segment $$[x, y] \in [L, R]$$, such that \(k | \prod_{i=x}^y a_i\). If there is no segment satisfying the condition, print $$-1$$.

Explanation

In the first query, $$[2,7]$$ the segment $$[3,4]$$ belongs to it and has the product $$6$$ which is divisible by $$k=6$$. Its size is $$2$$ so the answer for that query is $$2$$.

Time Limit:
2.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB