# Alternating LG Queries solution codechef

## Alternating LG Queries solution codechef

You are given an array AA consisting of NN integers. You have to answer QQ queries of the following two types:

• 11 LL RR (R>L)(R>L) which asks you to find gcd(AL,lcm(AL+1,gcd(AL+2,...,((RL)mod2==1?gcd(AL,lcm(AL+1,gcd(AL+2,…,((R−L)mod2==1? gcd(AR1,AR):lcm(AR1,AR)))))gcd(AR−1,AR):lcm(AR−1,AR))…))).

• 22 LL RR (R>L)(R>L) which asks you to find the same as above but lcmlcm swapped with gcdgcd and vice-versa.

Here lcm(a,b)lcm(a,b) and gcd(a,b)gcd(a,b) denotes the least common multiple and greatest common divisor of two integers aa and bb respectively.

Example: Consider the array AA = [2,4,8,16,32,64][2,4,8,16,32,64].

• Suppose a query is of the form 11 11 66, so it asks you to find: gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64)))))gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64))))).

• Suppose a query is of the form 22 11 55, so it asks you to find: lcm(2,gcd(4,lcm(8,gcd(16,32))))lcm(2,gcd(4,lcm(8,gcd(16,32)))).

Note: Since input-output is large, prefer using fast input-output methods.

### Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• Each testcase contains Q+2Q+2 lines of input.
• The first line of each test case contains two space-separated integers, NN and QQ.
• The second line of each test case contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.
• QQ lines follow. For each valid ii, the ithith of these lines contains three space-separated integers Typei,Li,RiTypei,Li,Ri, the type and parameters of the ithith query.

### Output Format

For each query, output in a single line answer to the problem.

### Constraints

• 1T31≤T≤3
• 2N21052≤N≤2⋅105
• 1Q21051≤Q≤2⋅105
• 1Ai1091≤Ai≤109
• 1Typei21≤Typei≤2
• 1Li<RiN1≤Li<Ri≤N
• The sum of NN over all test cases does not exceed 21052⋅105.
• The sum of QQ over all test cases does not exceed 21052⋅105.

• 2N6302≤N≤630
• The sum of NN over all test cases does not exceed 630630.
• Time limit: 11 sec

• Original constraints
• Time limit: 1.51.5 sec

### Sample Input 1

1
6 3
2 4 8 16 32 64
1 1 6
2 1 5
1 5 6


### Sample Output 1

2
4
32


### Explanation

Test case 11: The answer for the first query is =gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64)))))=gcd(2,lcm(4,gcd(8,lcm(16,gcd(32,64))))) == gcd(2,lcm(4,gcd(8,lcm(16,32))))gcd(2,lcm(4,gcd(8,lcm(16,32)))) = gcd(2,lcm(4,gcd(8,32)))gcd(2,lcm(4,gcd(8,32))) = gcd(2,lcm(4,8))gcd(2,lcm(4,8)) = gcd(2,8)gcd(2,8) = 22.

The answer for the second query is =lcm(2,gcd(4,lcm(8,gcd(16,32))))=lcm(2,gcd(4,lcm(8,gcd(16,32)))) = lcm(2,gcd(4,lcm(8,16)))lcm(2,gcd(4,lcm(8,16))) = lcm(2,gcd(4,16))lcm(2,gcd(4,16)) = lcm(2,4)lcm(2,4) = 44.