Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Paltu, a Prime Lover

By Sajjat004 · Limits 1s, 64 MB

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. 1iN, 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.

Input

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 ≤ 105
1 ≤ A[i], V ≤ 108
1 ≤ LRN

Output

For each query of type 2, Print the numbers of prime from X to Y (Inclusive) (X and Y are described in the problem).

Sample

InputOutput
10 3
1 2 3 4 5 6 7 8 9 10
2 3 7
1 8 2
2 6 10
3
4

Discussion

Statistics


71% Solution Ratio

prodip_bsmrstuEarliest, 1w ago

JONTRONAFastest, 0.3s

prodip_bsmrstuLightest, 21 MB

steinumShortest, 1919B

Submit

Login to submit