CF1422F.Boring Queries

Yura owns a quite ordinary and boring array $a$ of length $n$. You think there is nothing more boring than that, but Vladik doesn't agree!

In order to make Yura's array even more boring, Vladik makes $q$ boring queries. Each query consists of two integers $x$ and $y$. Before answering a query, the bounds $l$ and $r$ for this query are calculated: $l = (last + x) \bmod n + 1$, $r = (last + y) \bmod n + 1$, where $last$ is the answer on the previous query (zero initially), and $\bmod$ is the remainder operation. Whenever $l \gt r$, they are swapped.

After Vladik computes $l$ and $r$ for a query, he is to compute the least common multiple (LCM) on the segment $[l; r]$ of the initial array $a$ modulo $10^9 + 7$. LCM of a multiset of integers is the smallest positive integer that is divisible by all the elements of the multiset. The obtained LCM is the answer for this query.

Help Vladik and compute the answer for each query!

尤拉拥有一个非常普通且乏味的长度为 $n$ 的数组 $a$。你认为这已经无聊至极，但弗拉迪克却并不认同！

为了使尤拉的数组变得更加乏味，弗拉迪克会进行 $q$ 次“乏味”的查询。每次查询包含两个整数 $x$ 和 $y$。在回答每次查询前，需先计算该查询的边界 $l$ 和 $r$：

$$l = (last + x) \bmod n + 1,\quad r = (last + y) \bmod n + 1,$$

其中 $last$ 是上一次查询的答案（初始时为 $0$），$\bmod$ 表示取余运算。若计算得到 $l > r$，则交换 $l$ 与 $r$ 的值。

在弗拉迪克为某次查询算出 $l$ 和 $r$ 后，他需要计算原数组 $a$ 在区间 $[l; r]$ 上所有元素的最小公倍数（LCM），并对 $10^9 + 7$ 取模。一个整数多重集的 LCM 是能被该多重集中所有元素整除的最小正整数。该 LCM 即为本次查询的答案。

请帮助弗拉迪克，计算每次查询的答案！

The first line contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 2 \cdot 10^5$) — the elements of the array.

The third line contains a single integer $q$ ($1 \le q \le 10^5$) — the number of queries.

The next $q$ lines contain two integers $x$ and $y$ each ($1 \le x, y \le n$) — the description of the corresponding query.

第一行包含一个整数 $n$（$1 \le n \le 10^5$）—— 数组的长度。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 2 \cdot 10^5$）—— 数组的元素。

第三行包含一个整数 $q$（$1 \le q \le 10^5$）—— 查询的数量。

接下来的 $q$ 行，每行包含两个整数 $x$ 和 $y$（$1 \le x, y \le n$）—— 对应查询的描述。

Print $q$ integers — the answers for the queries.

输出 $q$ 个整数——各查询的答案。

Consider the example:

• boundaries for first query are $(0 + 1) \bmod 3 + 1 = 2$ and $(0 + 3) \bmod 3 + 1 = 1$. LCM for segment $[1, 2]$ is equal to $6$;
• boundaries for second query are $(6 + 3) \bmod 3 + 1 = 1$ and $(6 + 3) \bmod 3 + 1 = 1$. LCM for segment $[1, 1]$ is equal to $2$;
• boundaries for third query are $(2 + 2) \bmod 3 + 1 = 2$ and $(2 + 3) \bmod 3 + 1 = 3$. LCM for segment $[2, 3]$ is equal to $15$;
• boundaries for fourth query are $(15 + 2) \bmod 3 + 1 = 3$ and $(15 + 3) \bmod 3 + 1 = 1$. LCM for segment $[1, 3]$ is equal to $30$.

考虑如下示例：

• 第一个查询的边界为 $(0 + 1) \bmod 3 + 1 = 2$ 和 $(0 + 3) \bmod 3 + 1 = 1$，区间 $[1, 2]$ 的最小公倍数（LCM）为 $6$；
• 第二个查询的边界为 $(6 + 3) \bmod 3 + 1 = 1$ 和 $(6 + 3) \bmod 3 + 1 = 1$，区间 $[1, 1]$ 的最小公倍数为 $2$；
• 第三个查询的边界为 $(2 + 2) \bmod 3 + 1 = 2$ 和 $(2 + 3) \bmod 3 + 1 = 3$，区间 $[2, 3]$ 的最小公倍数为 $15$；
• 第四个查询的边界为 $(15 + 2) \bmod 3 + 1 = 3$ 和 $(15 + 3) \bmod 3 + 1 = 1$，区间 $[1, 3]$ 的最小公倍数为 $30$。