← 返回题目列表

Codeforces · 1493/D

D. 数组的 GCD

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的数组 $$$a$$$。要求您处理以下格式的 $$$q$$$ 查询:给定整数 $$$i$$$ 和 $$$x$$$,将 $$$a_i$$$ 乘以 $$$x$$$。

处理每个查询后,您需要输出数组 $$$a$$$ 的所有元素的最大公约数 (GCD)。

由于答案可能太大,因此要求您以 $$$10^9+7$$$ 为模输出。

输入

第一行包含两个整数 - $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — 更改之前数组 $$$a$$$ 的元素。

接下来的 $$$q$$$ 行包含以下格式的查询:每行包含两个整数 $$$i$$$ 和 $$$x$$$ ($$$1 \le i \le n$$$, $$$1 \le x \le 2 \cdot 10^5$$$)。

输出

打印 $$$q$$$ 行:处理每个查询后,在单独的行上输出所有元素模 $$$10^9+7$$$ 的 GCD。

示例

输入 #1

4 3
1 6 8 12
1 12
2 3
3 3

输出 #1

2
2
6

注意

第一次查询后,数组为 $$$[12, 6, 8, 12]$$$, $$$\operatorname{gcd}(12, 6, 8, 12) = 2$$$。

第二次查询后 — $$$[12, 18, 8, 12]$$$, $$$\operatorname{gcd}(12, 18, 8, 12) = 2$$$。

第三次查询后 — $$$[12, 18, 24, 12]$$$, $$$\operatorname{gcd}(12, 18, 24, 12) = 6$$$。

这里 $$$\operatorname{gcd}$$$ 函数表示最大公约数。