背景

GESP五级真题(202506)

描述

对于两个正整数 $a, b$ ，它们的最⼤公因数记为 $gcd(a, b)$ 。对于 $k \ge 3$ 个正整数 $c_1, c_2, ..., c_k$，它们的最⼤公因数为：

$$gcd(c_1, c_2, ..., c_k) = gcd(gcd(c1, c2, ..., c_{k-1}), c_k) $$

给定 $n$ 个正整数 $a_1, a_2, ..., a_n$ 以及 $q$ 组询问。对于第 $i$ （$1 \le i \le q$ ）组询问，请求出 $a_1 + i, a_2 + i, ..., a_n + i$ 的最⼤公因数，也即 $gcd(a_1 + i, a_2 + i, ..., a_n + i$ 。

格式

输入

第⼀⾏，两个正整数 $n, q$ ，分别表⽰给定正整数的数量，以及询问组数。

第⼆⾏， $n$ 个正整数 $a_1, a_2, ..., a_n$ 。

输出

输出共 $q$ ⾏，第 $i$ ⾏包含⼀个正整数，表⽰ $a_1 + i, a_2 + i, ..., a_n + i$ 的最⼤公因数。

样例

5 3
6 9 12 18 30

1
1
3

3 5
31 47 59

4
1
2
1
4

数据规模

对于 60 % 的测试点，保证 $1 \le n \le 10^3， 1 \le q \le 10$。 对于所有测试点，保证 $ 1 \le n \le 10^5， 1 \le q \le 10^5, 1 \le a_i \le 1000 $。

限制

时间限制：1.0 s

空间限制：512.0 MB