Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Q. Quirky Queries
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Eugene is playing with a sequence a1, a2, ..., an of quirky integers. Henry challenged Eugene to answer the following queries:

  • Query of type 1 l r x: for all ai in the range [l, r], change ai to x if the sorted sequence of divisors of x is lexicographically smaller than the sorted sequence of divisors of ai. 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 109 + 7.
Eugene needs to answer these quirky queries quickly! Can you help him?
Input

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

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 107). It is guaranteed that each ai is quirky.

The third line contains a positive integer q (1 ≤ q ≤ 2·105): 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 ≤ 107): 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 109 + 7.

Examples
Input
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