最大公因数

题目描述

对于两个正整数 a,b，它们的最大公因数记为 gcd(a,b)。对于k≥3个正整数 c₁,c₂,……,c_k，它们的最大公因数为:

gcd(c₁,c₂,……,c_k)=gcd(gcd(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，分别表示给定正整数的数量，以及询问组数。

第二行，几个正整数 a₁,a₂,……,a_n。

输出格式

输出共q行，第i行包含一个正整数，表示 a₁ +i,a₂+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

数据范围

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

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