PRMQUER - Prime queries

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^7.

No number in the 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 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

ID RESULT TIME
code...



Added by:Rishav Goyal
Date:2014-04-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own

hide comments
2014-12-19 11:49:14 arjundabra
finally AC nice ques...
2014-12-19 09:21:41 arjundabra
@Rishav Goyal
Can you please tell me why i am getting wrong answer on test 4.
2014-11-11 15:57:12 Luis Manuel D�az Bar�n
Finally Accepted. This is a bit hard than this problem:
http://www.spoj.com/problems/CNTPRIME/
2014-07-27 17:45:10 [Lakshman]
@Rishav Goyal Can you please tell me where my code fails.

Thanks

Reply(Rishav) --> check your replace operation. it's not working fine. think for a moment.

Lakshman-->You mean My range updated part is not okay?

reply(Rishav) : i can't check the code exactly, but i have a input 'R a l r,A V l, R a l r' followed by Q. and its not working fine. yeah one more thing is your output is 10 times greater the expected output. You shoud read the problem once more. Check Query Operation once more, to see what u are supposed to do.

Last edit: 2014-07-28 10:11:02
2014-07-17 10:46:03 Archit Jain
After tonnes of wa finally AC


Last edit: 2014-07-26 14:45:33
2014-07-17 01:29:36 [Lakshman]
@Rishav Goyal can you please tell me why I am getting segmentation fault .
Thanks.
2014-06-09 13:35:25 Jashan Goyal
id -11728782
@Rishav Goyal
please see my solution
I am getting NZEC error but it runs fine on ideone.

Last edit: 2014-06-09 14:16:16
2014-04-25 14:42:11 ivar.raknahs
@Rishav Goyal
is switch case causing TLE.(id 11491630)

@reply : Why would switch case results TLE ? absolutely Not.
Order must be something like O(log) for each query. Solve some easy problem first like Lazy propagation, segment tree.

Last edit: 2014-04-26 12:33:50
2014-04-18 18:31:11 ivar.raknahs
id-11463512
@Rishav Goyal
plz check my solution its continuously giving run time error after judge 4.
its perfectly running on ideone

reply : Even if you pass run time error, you will get TLE bcz your solution is not optimized.

Last edit: 2014-04-19 15:30:57
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.