对于两个正整数 a, b，它们的最大公因数记为 \gcd(a, b)。对于 k \geq 3 个正整数 c_1, c_2, \ldots, c_k，它们的最大公因数为： \gcd(c_1, c_2, \ldots, c_k) = \gcd(\gcd(c_1, c_2, \ldots, c_{k-1}), c_k)

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

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

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

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

数据范围

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

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