Problem Description
The greatest common divisor (gcd) of two or more integers (at least one of which is not zero) is the largest positive integer that divides the numbers without a remainder.
Now I will give you a simple problem about gcd again.
Given a sequence of N integers, A = {a1, a2, ..., aN }.
For every pair of < l, r >( 1 ≤ l ≤ r ≤ N ), defined a function F (l, r) = gcd(ai)( l ≤ i ≤ r ) that is the greatest common divisor of all the integers in the subsequence {al, al+1, ..., ar }
Obviously, There are N * (N + 1)/2 pair of < l, r >( 1 ≤ l ≤ r ≤ N ). We can get the rank of pair < l, r > through the following code.
1 pair get_RANK(int l,int r)
2 {
3 mapmp;
4 int k1 = 1, k2 = 1;
5 for(int i = 1;i <= N;i++)
6 for(int j = i;j <= N;j++)
7 {
8 if(i == l && j == r)continue;
9 if(F(i,j) < F(l,r))
10 {
11 if(mp.find(F(i,j)) != mp.end())continue;
12 k1++;
13 mp[F(i,j)] = 1;
14 }
15 else if(F(i,j) == F(l,r))
16 {
17 if(i < l || (i == l && j < r))k2++;
18 }
19 }
20 return make_pair(k1,k2);
21 }
(If you don’t know C++, what a sad story! Sorry!)
There are Q queries, you need to answer the following two queries:
● SELECT k1 k2: ask for the pair < l, r > which is rank < k1, k2 >.If there is no such pair output -1.
● RANK l r: ask for the rank < k1, k2 > of the pair < l, r >
Input
The first line of the input is T (1 ≤ T ≤ 10), which stands for the number of test cases you need to solve.
The first line of each case contains two integers N ,Q (1 ≤ N, Q ≤105),denoting the number of integers and queries, respectively.
The second line contains N integers, a1, a2, ..., aN (1 ≤ ai ≤ 105).
For the next Q lines, contain instructions “SELECT k1 k2” or “RANK l r” (1 ≤ k1, k2 ≤ N * (N + 1)/2,1 ≤ l ≤ r ≤ N ),
Output
For each test case, print a line “Case #t:”(without quotes, t means the index of the test case) at the beginning.
For each query, output the answer.
Sample Input
1
3 6
6 2 4
RANK 1 1
SELECT 3 1
RANK 2 3
SELECT 2 2
SELECT 1 3
SELECT 1 4
Sample Output
Case #1:
3 1
1 1
1 4
-1
2 2
2 3