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:
A V l
, Add the value V to element with index l.R a l r
, Replace all the elements of sequence with index i s.t. l <= i <= r with a.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
hide comments
sultania23:
20170319 05:49:04
properly look input format and range otherwise runtime error or wrong answer..


hodobox:
20160613 22:03:56
I got AC assuming 0 <= A[i] <= 2^32 at all times Last edit: 20160617 04:20:59 

sachinsahoo11:
20160602 22:44:16
can the numbers in the array go negative at any point? 

[deleted]:
20150211 09:34:06
Can V be negative ? 

arjundabra:
20141219 11:49:14
finally AC nice ques... 

arjundabra:
20141219 09:21:41
@Rishav Goyal


Luis Manuel Dï¿½az Barï¿½n:
20141111 15:57:12
Finally Accepted. This is a bit hard than this problem:


[Lakshman]:
20140727 17:45:10
@Rishav Goyal Can you please tell me where my code fails.


Archit Jain:
20140717 10:46:03
After tonnes of wa finally AC


[Lakshman]:
20140717 01:29:36
@Rishav Goyal can you please tell me why I am getting segmentation fault .

Added by:  Rishav Goyal 
Date:  20140416 
Time limit:  0.649s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Own 