题目描述

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

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

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

输入格式

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

第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$。

输出格式

输出共 $q$ 行，第 $i$ 行包含一个正整数，表示 $a_1+i, a_2+i, \dots, 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

说明

数据范围

• 对于 $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$。
• 保证所有的输入数值均为整数。