最大公因数

题目描述

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

$\gcd(c_1, c_2, \ldots, c_k) = \gcd(\gcd(c_1, c_2, \ldots, c_{k-1}), c_k)$

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

输入格式

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

第二行，$n$ 个正整数 $a_1, a_2, \ldots, a_n$。

输出格式

输出共 $q$ 行，第 $i$ 行包含一个正整数，表示 $a_1 + i, a_2 + i, \ldots, a_n + i$ 的最大公因数。

样例1

输入：

5 3
6 9 12 18 30

输出：

1
1
3

样例解释1

无（原卷未提供样例解释）。

样例2

输入：

3 5
31 47 59

输出：

4
1
2
1
4

样例解释2

无（原卷未提供样例解释）。

数据范围

对于 $60\%$ 的测试点，保证 $1 \le n \le 10^4$，$1 \le q \le 10$。

对于所有测试点，保证 $1 \le n \le 10^6$，$1 \le q \le 10^5$，$1 \le a_i \le 1000$。