Problem L
Pairs and Common

Bob starts out with an ordered list $a$ of $N$ positive integers $a_i$ $(1 \leq i \leq N)$. He then performs a total of $Q$ actions that can be of one of two types:

• $1$ $x$ $y$: Bob adds $x$ copies of value $y$ to the end of the list, whereby $y$ is a prime number.

• $2$ $l$ $r$: Bob asks you to compute the number of pairs $(a_i,a_j)$ whose greatest common divisor lies in the interval $[l, r]$. That is, to count the number of pairs such that $i < j$ and $l \leq \gcd (a_i,a_j) \leq r$. Since this number can be very large, output its remainder when divided by $10^9 + 7$.

Note that while the original list may contain arbitrary positive integers, type $1$ queries will add only prime numbers.

Input

The first line contains one integer $N$ $(1 \leq N \leq 10^6).$ The second line contains $N$ integers $a_i$ $(1 \leq a_i \leq 10^6).$ The third line contains one integer $Q = P + M$ $(1 \leq Q \leq 2 \cdot 10^5)$, where $P$ and $M$ are the numbers of queries of type $1$ and $2$, respectively.

Each of the next $Q$ lines starts with an integer $t \in \{ 1, 2\} $:

• If $t = 1$, it is followed by two integers $x$ and $y$ $(1 \leq x,y \leq 10^6)$ where $y$ is prime.

• If $t = 2$, it is followed by two integers $l$ and $r$ $(1 \leq l \leq r \leq 10^6).$

Output

Output $M$ nonnegative integers on $M$ lines, which are the answers for the $M$ queries of type $2$. Remember to output each number modulo $10^9+7$.

3
1 2 3
3
1 2 3
2 2 3
2 1 2

3
7