Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Easy Prime!

By tahmedge · Limits 1s, 512 MB

There are N numbers in an array. You will have Q queries. In each query, you can make 2 operations. These are:

  • 1 X Y: This will print total number of prime numbers in the range X & Y (inclusive).

  • 2 X a: This will update the value at index X with the value a. If previous value at index X is b, then it will now be updated as a.

All indexes are 1-based.

Input

In the first line take N (1 ≤ N ≤ 105) as input, then in the next line take N numbers as input in your array. The next line of input will take Q (1 ≤ Q ≤ 105). It indicates the total number of queries. Then next Q lines will contain the queries. The maximum value of prime number is 107.

Output

For each input, print the total number of primes in the range X and Y (inclusive).

Sample

InputOutput
10 
12 9 29 14 9 76 7 6 8 10
5
1 1 4
2 4 29
1 1 4
2 1 29
1 1 4
1
2
3

Discussion

Statistics


76% Solution Ratio

mamun4122Earliest, Jun '17

TurinhstuFastest, 0.0s

MustangLightest, 393 kB

AdnanAlMaruf_9Shortest, 713B

Submit

Login to submit

Related Contests

Intra LU Programming Contest Summer 2017 Ended at 2017-06-08 10:15:00 +0000 UTC
Replay of Intra LU Programming Contest Summer 2017 Ended at 2017-06-12 19:30:00 +0000 UTC
BRACU Intra Programming Contest Fall 2018 (Senior) Ended at 2018-09-28 12:30:00 +0000 UTC