GCD pair

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 = {a₁, a₂, ..., a_N }.

For every pair of < l, r >( 1 ≤ l ≤ r ≤ N ), defined a function F (l, r) = gcd(a_i)( l ≤ i ≤ r ) that is the greatest common divisor of all the integers in the subsequence {a_l, a_l+1, ..., a_r }

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<int,int> get_RANK(int l,int r)
2 {
3 map<int,int>mp;
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 < k₁, k₂ >.If there is no such pair output -1.

● RANK l r: ask for the rank < k₁, k₂ > of the pair < l, r >

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 ≤10⁵),denoting the number of integers and queries, respectively.

The second line contains N integers, a₁, a₂, ..., a_N (1 ≤ a_i ≤ 10⁵).

For the next Q lines, contain instructions “SELECT k₁ k₂” or “RANK l r” (1 ≤ k₁, k₂ ≤ N * (N + 1)/2,1 ≤ l ≤ r ≤ N ),

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.

1
3 6
6 2 4
RANK 1 1
SELECT 3 1
RANK 2 3
SELECT 2 2
SELECT 1 3
SELECT 1 4

Case #1:
3 1
1 1
1 4
-1
2 2
2 3

2014 ACM/ICPC Asia Regional Shanghai Online