Mojtaba's Array and Arpa's Queries
/

## Advanced Data Structures, Data Structures, Fenwick tree

Problem
Editorial
Analytics

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$.

SAMPLE INPUT
10 6 10
9 5 2 3 1 1 10 2 9 4
2 7
7 8
7 7
2 7
4 7
7 8
1 3
2 8
3 5
1 9

SAMPLE OUTPUT
2 -1 -1 2 4 -1 3 2 2 2

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

## This Problem was Asked in

Initializing Code Editor...