## PRMQUER - Prime queries

You are given a simple task.

Given a sequence A[i] with N numbers s.t. 1 <= i <= N. You have to perform Q operations on a given set of numbers.

Operations:

1. `A V l`, Add the value V to element with index l.
2. `R a l r`, Replace all the elements of sequence with index i s.t. l <= i <= r with a.
3. `Q l r`, Print the Number of elements with index i s.t. l <= i <= r and A[i] is prime number and A[i] <= 10^7.

No Number In sequence ever will exceed 10^9.

### Constraints

• 1 <= N <= 10^5
• 1 <= Q <= 10^5
• V <= 10^3
• A[i] <= 10^8
• a <= 10^7,  1 <= l <= r <=N.

### Input

First line contains N as Number of sequence elements && Q as number of operations to be performed. Second line contains Initial N elements of the sequence. After that each of the next Q lines contains one operation to be performed on the sequence.

### Output

Print each value in newline as stated above.

```5 10
1 2 3 4 5
A 3 1
Q 1 3
R 5 2 4
A 1 1
Q 1 1
Q 1 2
Q 1 4
A 3 5
Q 5 5
Q 1 5```

```2
1
2
4
0
4```