Eugene, the number theorist, is studying some #cf_span(class=[tex-font-style-underline], body=[quirky]) integers. An integer x is #cf_span(class=[tex-font-style-underline], body=[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:
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 .
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.
For each query of type 2 l r, output modulo 109 + 7.
## 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.
[samples]
**Definitions**
Let $ \mathcal{Q} \subset \mathbb{Z}^+ $ be the set of *quirky* integers:
$ x \in \mathcal{Q} $ if and only if:
- $ \nexists \, k \in \mathbb{Z}^+ $ such that $ k^2 \mid x $, and
- $ \nexists \, p \in \mathbb{P} $ with $ p \geq 300 $ such that $ p \mid x $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of quirky integers.
For any $ x \in \mathcal{Q} $, let $ D(x) $ denote the *sorted list of positive divisors* of $ x $, ordered increasingly.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq a_i \leq 10^7 $ and $ a_i \in \mathcal{Q} $ for all $ i \in \{1, \dots, n\} $
3. $ 1 \leq q \leq 2 \cdot 10^5 $
4. For each query:
- Type 1: $ 1 \; l \; r \; x $, where $ x \in \mathcal{Q} $, $ 1 \leq l \leq r \leq n $
- Type 2: $ 2 \; l \; r $, where $ 1 \leq l \leq r \leq n $
**Operations**
- **Type 1 Query ($ 1 \; l \; r \; x $)**:
For each $ i \in \{l, \dots, r\} $, if $ D(x) \succ D(a_i) $ (lexicographically), then set $ a_i \leftarrow x $.
- **Type 2 Query ($ 2 \; l \; r $)**:
Output $ \left( \sum_{i=l}^{r} a_i \right) \bmod (10^9 + 7) $.
**Objective**
Process $ q $ queries and output the result for each type-2 query.