# Practice on Toph

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

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

**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** ≤ 10^{5}

1 ≤ **A**[i], **V** ≤ 10^{8}

1 ≤ **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).

Input | Output |
---|---|

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

71% Solution Ratio

prodip_bsmrstuEarliest,

JONTRONAFastest, 0.3s

prodip_bsmrstuLightest, 21 MB

steinumShortest, 1919B

Login to submit