All Tracks Data Structures Advanced Data Structures Fenwick (Binary Indexed) Trees Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?