题目描述

对于两个正整数 $a,b$ ，它们的最⼤公因数记为 $\text gcd(a,b)$ 。对于 $k \geq 3$ 个正整数 $c_1,c_2, \dots , c_k$，它们的最⼤公因数为：

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

给定 $n$ 个正整数 $a_1,a_2, \dots ,a_n$ 以及 $q$ 组询问。对于第 $i$ （$1 \leq i \leq 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$ 的最⼤公因数。

输入输出样例 #1

5 3
6 9 12 18 30

1
1
3

输入输出样例 #2

3 5
31 47 59

4
1
2
1
4

数据说明

对于60%的测试点，保证 $1 \leq n \leq 1000，1 \leq q \leq 10$。

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