Reference: Codeforces 1458A — Row GCD

You are given two sequences of positive integers:

~a_1, a_2, \ldots, a_n~

and

~b_1, b_2, \ldots, b_m~

For every ~j~ from ~1~ to ~m~, find:

~gcd(a_1 + b_j, a_2 + b_j, \ldots, a_n + b_j)~

Input

• The first line contains two integers: ~n~ and ~m~.
• The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.
• The third line contains ~m~ integers: ~b_1, b_2, \ldots, b_m~.

Output

• Print ~m~ integers. The ~j~-th integer must be ~gcd(a_1 + b_j, a_2 + b_j, \ldots, a_n + b_j)~.

Constraints

• ~1 \le n, m \le 2 \times 10^5~
• ~1 \le a_i \le 10^{18}~
• ~1 \le b_j \le 10^{18}~

Example 1

Input:

4 4
1 25 121 169
1 2 7 23

Output:

2 3 8 24