You are given a simple task.

Given a sequence A[i] with N numbers such that 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 such that l ≤ i ≤ r with a.
3. Q l r, Print the number of elements with index i such that l ≤ i ≤ r and A[i] is prime number and A[i] ≤ 10⁷.

No number in the sequence ever will exceed 10⁹.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ Q ≤ 10⁵
• V ≤ 10³
• A[i] ≤ 10⁸
• a ≤ 10⁷
• 1 ≤ l ≤ r ≤ N.

Input

First line contains N as number of sequence elements and Q as number of operations to be performed. Second line contains N initial 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