Description

对于两个正整数a, b，它们的最大公因数记为 gcd(a, b)。

对于 k>=3个正整数c1, c2, c3, ...... ck，它们的最大公因数为：gcd(c1, c2, c3, ...... ck) = gcd(gcd(c1, c2, c3, ...... ck-1), ck)

给定 n 个正整数 a1, a2, a3, ...... an 以及 q 组询问。对于第 i（ 1<=i<=q）组询问，请求出 a1+i, a2+i, a3+i, ......an+i 的最大公因数，也即 gcd(a1+i, a2+2, a3+i, ......an+i)。

Input Format

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

第二行， n个正整数a1, a2, a3, ...... an。

Output Format

输出共 q 行，第 i 行包含一个正整数，表示a1+i, a2+2, a3+i, ......an+i的最大公因数。

5 3
6 9 12 18 30

1
1
3

3 5
31 47 59

4
1
2
1
4

Hint

对于 60% 的测试点，保证 1<=n<=1000，1<=q<=10 。

对于所有测试点，保证1<=n<=100000，1<=q<=1000, 1<=ai<=1000。

Source