题目描述

对于两个正整数 (a, b)，它们的最大公因数记为gcd(a, b)。对于 (k ≥3) 个正整数 (c1, c2....ck )，它们的最大公因数为：
gcd(c1,c2....,ck)=gcd(gcd(c1,c2....c(k-1))) 给定 (n) 个正整数 (a1,a2,....,an) 以及 (q) 组询问。对于第 i(1≤i≤q) 组询问，请求出a1+i,a2+i,...an+i 的最大公因数，也即 (gcd(a1 + i, a2 + i,..., an + i))。

输入格式

第一行，两个正整数 (n, q)，分别表示给定正整数的数量，以及询问组数。
第二行，(n) 个正整数 (a1, a2,..., an)。

输出格式

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

样例

输入样例 1

5 3  
6 6 6 6 6  

输出样例 1

1  
1  
3  

输入样例 2

3 5  
1 31 1  

输出样例 2

4  
1  
2  
1  
4  

数据范围

• 对于 60% 的测试点，保证 (1 ≤ n≤ $10^3$, 1 ≤q ≤ 10)。
• 对于所有测试点，保证 (1 ≤ n ≤ $10^5$, 1 ≤ q ≤ $10^5$, 1≤ ai ≤ 1000)。