最大公因数

题目描述

对于两个正整数 a,b，他们的最大公因数记为 \gcd(a,b)。对于 k > 3 个正整数 c_1,c_2,\dots,c_k，他们的最大公因数为：

$\gcd(c_1,c_2,\dots,c_k)=\gcd(\gcd(c_1,c2,\dots,c{k-1}),c_k)$

给定 n 个正整数 a_1,a_2,\dots,a_n 以及 q 组询问。对于第 i(1 \le i \le q) 组询问，请求出 a_1+i,a_2+i,\dots,a_n+i 的最大公因数，也即 \gcd(a_1+i,a_2+i,\dots,a_n+i)。

输入

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

第二行，n 个正整数 a_1,a_2,\dots,a_n。

输出

输出共 q 行，第 i 行包含一个正整数，表示 a_1+i,a_2+i,\dots,a_n+i 的最大公因数。

样例

提示

对于 60\% 的测试点，保证 1 \le n \le 10^3，1 \le q \le 10。

对于所有测试点，保证 1 \le n \le 10^5，1 \le q \le 10^5，1 \le a_i \le 1000。

来源

GESP