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.
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.
For each input, print the total number of primes in the range X and Y (inclusive).
Input | Output |
---|---|
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 |