F. 无聊的查询
时间限制：每个测试点 $3$ 秒
内存限制：$512$ 兆字节

Yura 有一个相当普通且无聊的数组 $a$，长度为 $n$。你认为没有比这更无聊的东西了，但 Vladik 不同意！

为了让 Yura 的数组更加无聊，Vladik 会进行 $q$ 个无聊的查询。每个查询由两个整数 $x$ 和 $y$ 组成。在回答查询之前，会先计算出本次查询的边界 $l$ 和 $r$：

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

其中 $\text{last}$ 是上一个查询的答案（初始为 $0$），$\bmod$ 是取余运算。如果 $l > r$，则将它们交换。

计算出 $l$ 和 $r$ 后，Vladik 需要计算初始数组 $a$ 在区间 $[l; r]$ 上的最小公倍数，并对 $10^9+7$ 取模。一个多重集的最小公倍数是指能被该多重集中所有元素整除的最小正整数。计算出的 LCM 就是本次查询的答案。

请帮助 Vladik 计算每个查询的答案！

---

输入格式
第一行包含一个整数 $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$）——对应查询的描述。

---

输出格式
输出 $q$ 行，每行一个整数——查询的答案。

---

样例输入

3
2 3 5
4
1 3
3 3
2 3
2 3

样例输出

6
2
15
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]$ 的 LCM 是 $2$；
• 第三个查询的边界为 $(2+2)\bmod 3+1=2$ 和 $(2+3)\bmod 3+1=3$，区间 $[2,3]$ 的 LCM 是 $15$；
• 第四个查询的边界为 $(15+2)\bmod 3+1=3$ 和 $(15+3)\bmod 3+1=1$，区间 $[1,3]$ 的 LCM 是 $30$。