Yura 拥有一个相当普通且无聊的数组 $$$a$$$,长度为 $$$n$$$。你认为没有什么比这更无聊的了,但弗拉迪克不同意!
为了让 Yura 的数组更加无聊,Vladik 进行了 $$$q$$$ 无聊的查询。每个查询由两个整数 $$$x$$$ 和 $$$y$$$ 组成。在回答查询之前,计算此查询的边界 $$$l$$$ 和 $$$r$$$:$$$l = (last + x) \bmod n + 1$$$、$$$r = (last + y) \bmod n + 1$$$,其中 $$$last$$$ 是上一个查询的答案(最初为零),$$$\bmod$$$ 是余数运算。每当 $$$l > r$$$ 时,它们就会被交换。
Vladik 计算完查询的 $$$l$$$ 和 $$$r$$$ 后,他将计算段 $$$[l; 上的最小公倍数 (LCM); r]$$$ 初始数组 $$$a$$$ 模 $$$10^9 + 7$$$。整数多重集的 LCM 是可被多重集的所有元素整除的最小正整数。获得的 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$$$ 整数 — 查询的答案。
示例
输入 #1
3 2 3 5 4 1 3 3 3 2 3 2 3
输出 #1
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$$$。