CF1493D.GCD of an Array

You are given an array $a$ of length $n$. You are asked to process $q$ queries of the following format: given integers $i$ and $x$, multiply $a_i$ by $x$.

After processing each query you need to output the greatest common divisor (GCD) of all elements of the array $a$.

Since the answer can be too large, you are asked to output it modulo $10^9+7$.

给你一个长度为 $n$ 的数组 $a$。你需要处理 $q$ 个如下格式的查询：给定整数 $i$ 和 $x$，将 $a_i$ 乘以 $x$。

每次查询处理完毕后，你需要输出数组 $a$ 中所有元素的最大公约数（GCD）。

由于答案可能过大，你只需输出其对 $10^9+7$ 取模的结果。

The first line contains two integers — $n$ and $q$ ($1 \le n, q \le 2 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$) — the elements of the array $a$ before the changes.

The next $q$ lines contain queries in the following format: each line contains two integers $i$ and $x$ ($1 \le i \le n$, $1 \le x \le 2 \cdot 10^5$).

第一行包含两个整数 $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$）。

Print $q$ lines: after processing each query output the GCD of all elements modulo $10^9+7$ on a separate line.

输出 $q$ 行：每处理完一个查询后，在单独一行输出所有元素的最大公约数（GCD）对 $10^9+7$ 取模的结果。

After the first query the array is $[12, 6, 8, 12]$, $\operatorname{gcd}(12, 6, 8, 12) = 2$.

After the second query — $[12, 18, 8, 12]$, $\operatorname{gcd}(12, 18, 8, 12) = 2$.

After the third query — $[12, 18, 24, 12]$, $\operatorname{gcd}(12, 18, 24, 12) = 6$.

Here the $\operatorname{gcd}$ function denotes the greatest common divisor.

第一次查询后，数组变为 $[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}$ 函数表示最大公约数。