406238: GYM102319 Q Quirky Queries

Q. Quirky Queriestime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Eugene, the number theorist, is studying some quirky integers. An integer x is quirky if there is no integer k such that k² is a factor of x, and there is no prime number p ≥ 300 such that p divides x.

Eugene is playing with a sequence a₁, a₂, ..., a_n of quirky integers. Henry challenged Eugene to answer the following queries:

• Query of type 1 l r x: for all a_i in the range [l, r], change a_i to x if the sorted sequence of divisors of x is lexicographically smaller than the sorted sequence of divisors of a_i. It is guaranteed that x is quirky.

  For example, if Eugene had the integers 6, 10, 13 and the query 1 1 3 14, he would not change 6 or 10 since their sequences of divisors ( and respectively) are lexicographically smaller than 14's sequence , but he would change 13 to 14 since is lexicographically larger than .

• Query of type 2 l r: output modulo 10⁹ + 7.

Eugene needs to answer these quirky queries quickly! Can you help him?Input

The first line contains a positive integer n (1 ≤ n ≤ 10⁵).

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁷). It is guaranteed that each a_i is quirky.

The third line contains a positive integer q (1 ≤ q ≤ 2·10⁵): the number of queries. Then follow q lines, each of the form 1 l r x or 2 l r (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 10⁷): queries of type 1 or 2, respectively. It is guaranteed that x is quirky.

Output

For each query of type 2 l r, output modulo 10⁹ + 7.

ExamplesInput

3
6 10 13
5
1 1 3 14
2 1 1
2 2 2
2 3 3
2 1 3

Output

6
10
14
210

Input

1
6
5
2 1 1
1 1 1 2
2 1 1
1 1 1 1
2 1 1

Output

6
2
1