Euclid

After eating at Deadpool's restaurant and escaping from the Matrix, you are now asked to return to the ancient world. To the invention of the greatest common divisor, to be more precise.

In the beautiful city of Alexandria there is a vicious king. His kingdom consists of N cities displayed on a straight line, numbered from 1 to N. City i has to pay V_i coins initially, for 1 to N.

From time to time, the king increases some taxes or asks Euclid for the greatest number that divides all the taxes of cities in a given interval. You are given the initial array V. You have to perform Q operations on this array. There are two types of operations:

• query(a, b): compute gcd(V_a, V_{a+1}, ..., V_b).
• update(a, b, k): the king increases the taxes such that V_a += k, V_{a+1} += 2 × k, ..., V_b += (b - a + 1) × k.

The first line contains two integers N and Q, the number of cities and the number of operations. The second line contains N integers, the elements of array V. The following Q lines each contain one operation:

• If the operation is query(a, b), the line contains three integers: 0 a b.
• If the operation is update(a, b, k), the line contains four integers: 1 a b k.

Print the answer to each query operation on a separate line, in the order the queries were given.

• 1 ≤ N ≤ 100,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ a ≤ b ≤ N for all updates and queries
• 1 ≤ k ≤ 200,000,000 for all updates
• 1 ≤ V_i ≤ 200,000,000 for 1 ≤ i ≤ N

First operation: gcd(8, 12, 24) = 4.

Second operation: the array becomes 4 12 18 32 66 33 21 7.

Third operation: gcd(12, 18, 32) = 2.