最大公因数

题目描述

对于两个正整数 \(x, y\)，它们的最大公因数记为 \(\gcd(x, y)\)。给定 \(n\) 个正整数 \(a_1, a_2, \ldots, a_n\) 以及 \(q\) 组询问。对于第 \(i\)（\(1 \le i \le q\)）组询问，请求出 \(a_1+i, a_2+i, \ldots, a_n+i\) 的最大公因数。

输入格式

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

第二行，\(n\) 个正整数 \(a_i\)。

输出格式

输出共 \(q\) 行，第 \(i\) 行包含一个正整数，表示第 \(i\) 组询问的结果。

样例

输入样例 1

5 3
6 9 12 18 30

输出样例 1

1
1
3

数据范围

对于所有测试点，保证 \(1 \le n \le 10^5\)，\(1 \le q \le 10^4\)，\(1 \le a_i \le 10^9\)。（数据范围由题面字体缺字重建，取保守范围）