题目描述
对于两个正整数 a,b，他们的最大公因数记为 gcd(a,b)。对于 k>3 个正整数 c1,c2,…,ck，他们的最大公因数为：
gcd(c1,c2,…,ck)=gcd(gcd(c1,c2,…,ck−1),ck)
给定 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 的最大公因数。
输入输出样例
输入
5 3 6 9 12 18 30
输出
1 1 3
输入
3 5 31 47 59
输出
4 1 2 1 4
说明/提示
对于 60% 的测试点，保证 1≤n≤103，1≤q≤10。
对于所有测试点，保证 1≤n≤105，1≤q≤105，1≤ai≤1000。
