Shiv is fond of prime numbers. His girl friend priya found a list 'C' of numbers , she gave it to Shiv and started asking questions about the list. In each question she will given two numbers, L and R and Shiv must tell her the Largest prime number in C[L..R]. In order to make it more complicated, she started changing the numbers in between some questions.Help him to answer her questions.

Input:

First line of input has N and M , space separated , where N is the size of the list and where M is the number of queries.The second line has N space separated integers.
After this M lines follow, each line having q , the type of query, and two integers A and B, space separated. q can be either be 1 or 0. If q is 1 then output the largest prime number in C[A..B] ( both inclusive) . If q is 0 , priya has changed C[A] to B.

Output:
For each query in the test case output , in a single line , the largest prime number in the subpart, if no prime number exists output -1.

Constarints:

1 ≤ N, a , b ,M ≤ 10^5

1 ≤ C[i] ≤ 10^6

0 ≤ q ≤ 1

SAMPLE INPUT
3 2
1 2 3
0 2 1
1 1 2

SAMPLE OUTPUT
-1

见题面

见题面