最大公因数

题目描述

对于两个正整数 $a,b$，它们的最大公因数记为 $\gcd (a,b)$。对于 $k\ge 3$ 个正整数 $c_{1},c_{2},...,c_{k}$，它们的最大公因数为：

$\gcd (c_{1},c_{2},...,c_{k})=\gcd (\gcd (c_{1},c_{2},...,c_{k-1}),c_{k})$

给定 $n$ 个正整数 $a_{1},a_{2},...,a_{n}$ 以及 $q$ 组询问。对于第 $i$（$1\le i\le q$）组询问，请求出 $a_{1}+i,a_{2}+i,...,a_{n}+i$ 的最

大公因数，也即 $\gcd (a_{1}+i,a_{2}+i,...,a_{n}+i)$。

输入格式

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

第二行，$n$ 个正整数 $a_{1},a_{2},...,a_{n}$。

输出格式

输出共 $q$ 行，第 $i$ 行包含一个正整数，表示 $a_{1}+i,a_{2}+i,...,a_{n}+i$ 的最大公因数。

输入样例 1

15 326 9 12 18 30

输出样例 1

112133

输入样例 2

13 5231 47 59

输出样例 2

1421324154

数据范围

对于 $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$。