You are given a sequence a 1 ,a 2 ,...,a n consisting of positive integer.
You have to answer q queries:
A query is defined by a triplet of numbers (l i ,r i ,x i ). For each query, you have to find the largest
a p such that l i ≤ p ≤ r i and a p is coprime with x i or determine that there is no such a p
The first line of the input contains two integers n and p (1 ≤ n,q ≤ 10 5 ).
The second line contains n integers a 1 ,a 2 ,...a n (1 ≤ a i ≤ 10 5 , you can think that a i is generated
in random).
The next m lines contains queries. The i-th of these lines contains three integers
l i , r i , and x i . (1 ≤ l i ≤ r i ≤ n, 1 ≤ x i ≤ 10 5 ).
For each query, output the largest a p in a separate line. If there are no such a p output -1.
5 4
8 5 1 10 2
1 5 10
2 3 7
1 3 4
2 2 5
1
5
5
-1