All submissions for this problem are available.
You are given N prime numbers. You have to support Q queries, each of which is one of these :
- 1 i x : Update the ith element to x, where x is also a prime.
- 2 L R : Let S be the set of primes currently in range [L,R]. You need to first find X = product of all primes in set S and then find gcd(X, phi(X)) modulo 10^9 + 7. Note that a set only contains distinct elements, and that phi(X) is the euler totient function.
Can you process these queries quickly?
Input Format :The first line contains N, the number of integers.
The next line contains N spaces separated integers Pi, each of which is compulsorily a prime integer.
The next line contains Q, the number of queries. Each of the next Q lines contains 3 integers defining one of the queries as described above.
Output Format :For each query of type 2, output one integer : the answer to the query.
Constraints :1 <= N <= 10^5
1 <= Q <= 10^4
1 <= Pi, x <= 10^5
1 <= L <= R <= N
Sample Input :3
2 5 7
2 1 2
1 2 3
2 1 3
Sample Output :2
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, PAS fpc, PAS gpc, RUBY, PHP, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions