Description

给出两个正整数序列\(a,b\)，我们希望对于每个\(j(1<=j<=m)\)，求出\(gcd(a_1+b_j,a_2+b_j,...,a_n+b_j)\)。

Format

Input

包含不超过\(10\)组输入数据，请处理至文件结束。
每组数据第一行两个整数\(n,m(1<=n,m<=100000)\)，表示序列\(a\)和\(b\)的长度。
接下来一行\(n\)个整数表示序列\(a(1<=a_i<=10^{18})\)。
再下来一行\(m\)个整数表示序列\(b(1<=b_i<=10^{18})\)。

Output

对于每组数据输出一行，依次表示\(j\)为\(1\)到\(m\)时的答案，相邻两个整数用空格隔开，行末不要出现多余空格。

Sample 1

Input

4 4
1 25 121 169
1 2 7 23

Output

2 3 8 24

Limitation

2s, 1GB for each test case.

Source

Vijos Original