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.

Example

Input

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

Output

2
1
2
4
0
4