Our friend Ashu is a big Naruto aficionado and has been watching its episodes whole day. Its midnight now and he has just realized that tommorrow is the deadline for his maths assiggnment. So, he takes help of our another friend Kamboj. Kamboj being an expert in maths can easily solve the assiggnment but the assiggnment is too big for him to complete in time. Hence, he requires your help. The assignment consists of an array of N numbers having values in range of 1 to 10^6. There are Q queries that follow, each of either type mentioned below,

• 1 X Y -- you have to replace number on index X with Y
• 2 L R -- you have to output the number with maximum number of Distinct prime factors out of all numbers in range of indices [L,R]

Note-- If there are multiple answers, then output the largest one.

Input Format-

First line consists two space seperated numbers N and Q, size of the input array and number of queries repectively. Second line on N numbers that are in the input array. Each of the following Q lines consists of a query either of above two types mentioned in the statement.

Note--Indexing of array is from 1 to N.

Output Format-

For each query of type 2, ouput the required each in a separate line.

Constraints-

1 <= N <= 10^6

1 <= Q <= 10^6

1 <= A[i],Y <= 10^6

1 <= X <= N

1 <= L <= R <= N