statement.txt

Mirzapur's Election

Jas and Ashish are the President and Vice-president of CSIT Party and are working hard to win the elections of Mirzapur.

There are **N** states in Mirzapur, whose vote counts on Day 0 are given. (count[0....n-1])
Next **D** days, either the vote count of a state gets updated, or the election commission wants Jas and Ashish to submit their Max-Potential Value.

Max-Potential =  maximum of gcd(count[i],count[j]), for all pairs of states.( 0 <= i,j < n and i != j)

Mathematically, the two operations can be defined as:
[1 i x]: Update voteCount of state i to x. (count[i] = x)
[2]: Output Max-Potential of the current states.

Warning: Use Fast IO
Note: See the explantion of sample test cases, for more clarity.

Input
* The first line contains space-separated integers N, D.
* The second line contains N space-separated integers count[0],count[1] ...count[n-1].
* Next D line contains input corresponding to one of the operations mentioned below.
	* Operation 1:  1 i x (3 space-separarted integer)
	* Operation 2:  2

Output
For every operation of type 2, output the Max-Potential on a new line.

Constraints
* 1 < N <= 1e5
* 1 <= **D, x** <= 1e5
* 0 <= i < n
* 1 <= count[i] <= 1e5

Example Input
5 5
1 1 3 4 5
2
1 1 2
2
1 4 3
2

Example Output
1
2
3

Explanation
On Day 0, count = [1,1,3,4,5]
On Day 1, Max-Potential = 1, gcd of all pairs of states is 1.
On Day 2, count = [1,2,3,4,5]
On Day 3, Max-Potential = 2, gcd of states 1,3 is gcd(2,4) = 2.
On Day 4, count = [1,2,3,4,3]
On Day 5, Max-Potential = 3, gcd of states 2,4 is gcd(3,3) = 3.