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