蝈蝈的GCD

卢宝给了蝈蝈一串长度为n的数字序列a，下标为1~n。然后卢宝给蝈蝈一个下标p(1≤p≤n)，问蝈蝈是否存在最大的下标L(1≤L≤p)，使得区间[L,p]的gcd(a_l,a_l+1,……,a_p-1,a_p)恰好等于k，如果存在则输出这个最大的下标L，如果不存在，那么又问蝈蝈是否存在最小的下标R(p≤R≤n)，使得区间[p,R]的gcd(a_p,a_p+1,……,a_R-1,a_R)恰好等于k，如果存在则输出这个最小的下标R，反之输出-1

第一行两个整数 n 和 m ，分别表示序列长度和询问次数，每次询问都是独立的（1 ≤ n，m ≤ 100000）

第二行 n 个整数 a_i 表示序列 a （1 ≤ a_i ≤ 1e9）

接下来 m 行，每行表示一次询问

每行询问两个整数 p 和 k ，分别表示题面的下标和恰好等于的值（1 ≤ p ≤ n，0≤ k ≤ 1e9）

对每次询问输出一行题面中所说的最大的下标 L ，或者最小的下标 R ，或者 -1

5 5
1 2 2 6 3 
4 2
4 1
4 6
4 3
4 4

3
1
4
5
-1