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

hide comments
neach_joup: 2022-10-21 02:49:18

Long long!!!

Last edit: 2022-10-21 02:49:47
thesky233: 2022-10-01 14:04:17

notice that operation 3 says that <=10^7...
so if you got a RE please check whether the number is less than 10^7 first, then check if it is a prime number...

sabkx: 2022-04-29 14:18:51

ODT trash this

yaseenmollik: 2020-08-11 03:14:07

After tons of WA finally got it accepted! Nice problem.

setsugesuka: 2019-10-03 12:09:32

ODT can solve this problem easily..

sherlock11: 2018-06-29 06:09:05

read the 3rd query carefully it says <=10^7.....if u ignore this then AC will ignore u..:)

hackerwizard: 2018-05-19 18:39:29

Nice question learned something new

sultania23: 2017-03-19 05:49:04

properly look input format and range otherwise runtime error or wrong answer..
nice ques.

hodobox: 2016-06-13 22:03:56

I got AC assuming 0 <= A[i] <= 2^32 at all times

Last edit: 2016-06-17 04:20:59
sachinsahoo11: 2016-06-02 22:44:16

can the numbers in the array go negative at any point?


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