题目描述

对于两个正整数a，b，它们的最大公因数记为gcd(a,b)。对于k>=3个正整数c₁,c₂,c₃....c_k，它们的最大公因数为：

gcd(c₁,c₂,c₃...c_k)=gcd(gcd(c₁,c₂,c₃...c_k-1),c_k)

给定n个正整数a₁,a₂,...,a_n以及q组询问。对于第 i (1 <= i <= q) 组询问，请求出a₁+i,a₂+i,...a_n+i的最大公因数，也即gcd(a₁+i,a₂+i,...a_n+i)。

输入格式

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

输出格式

输出共q行，第i行包含一个正整数，表示a₁+i,a₂+i,...a_n+i的最大公因数。

样例 #1

样例输入 #1

5 3
6 9 12 18 30 

样例输出 #1

1
1
3

样例 #2

样例输入 #2

3 5
31 47 59

样例输出 #2

4
1
2
1
4

数据范围

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

对于所有测试点，保证1 <= n <= 10⁵，1 <= q <= 10⁵，1 <= a_i <= 1000。