题目描述

对于两个正整数 a, b，它们的最大公因数记为 gcd(a, b)。对于 k ≥ 3 个正整数 C₁, C₂, ..., Cₖ，它们的最大公因数为：

gcd(C₁, C₂, ..., Cₖ) = gcd(gcd(C₁, C₂, ..., Cₖ₋₁), Cₖ)

给定 n 个正整数 a₁, a₂, ..., aₙ 以及 Q 组询问。对于第 i（1 ≤ i ≤ Q）组询问，请求出 a₁+i, a₂+i, ..., aₙ+i 的最大公因数，也即 gcd(a₁+i, a₂+i, ..., aₙ+i)。

输入格式

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

第二行，n 个正整数 a₁, a₂, ..., aₙ。

输出格式

输出共 Q 行，第 i 行包含一个正整数，表示 a₁+i, a₂+i, ..., aₙ+i 的最大公因数。

样例

输入样例 1

5 3
6 9 12 18 30

输出样例 1

1
1
3

输入样例 2

3 5
31 47 59

输出样例 2

4
1
2
1
4

数据范围

对于 60% 的测试点，保证 1 ≤ n ≤ 1000，1 ≤ Q ≤ 10。

对于所有测试点，保证 1 ≤ n ≤ 1e5，1 ≤ Q ≤ 1e5，1 ≤ i ≤ 1000。