最大公因数

题目描述

对于两个正整数 $a,b$，它们的最大公因数记为 $\gcd(a,b)$。对于 $k\ge 3$ 个正整数，$c_1，c_2,.....,c_k$，它们的最大公因数为： $$\gcd(c_1，c_2,.....,c_k) = \gcd(\gcd(c_1，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$ 的最大公因数。

输入样例 1

5 3
6 9 12 18 30

输出样例 1

1
1
3

输入样例 2

3 5
31 47 59

输出样例 2

4
1
2
1
4