Note that the memory limit is unusual.
Paltu is a good programmer and he loves prime numbers. One day, his friend gave him a challenge to solve a problem. The problem are described in below.
There will be given a array A with N integers ( Indexed from 1 to N ) and Q queries to perform on the array.
Query type 1:1 i V : Set the value of the i’th element to V i.e. 1 ≤ i ≤ N, A[i] = V.
Query type 2:2 L R : Let X be the minimum value in the array A from the index L to R (Inclusive) and Y be the maximum value in the array A from the index L to R (Inclusive) . Now print the numbers of prime from X to Y (Inclusive).
Due to Ramadan, Paltu is quite busy. So he asked you to solve the problem.
The first line of input contains two integers N (the number of integers) and Q (the number of queries)Next line contains N space separated integers.Each of the next Q lines contains a task in one of the query.
Constrains:1 ≤ N, Q ≤ 1051 ≤ A[i], V ≤ 1081 ≤ L ≤ R ≤ N
For each query of type 2, Print the numbers of prime from X to Y (Inclusive) (X and Y are described in the problem).
10 3 1 2 3 4 5 6 7 8 9 10 2 3 7 1 8 2 2 6 10