Cho 2 dãy số nguyên dương ~a~ có ~n~ phần tử và ~b~ có ~m~ phần tử. Với ~j~ từ 1 đến ~m~ hãy tìm ~gcd(a_1 + b_j, a_2 + b_j,...,a_n + b_j)~.

Input

• Dòng đầu tiên gồm 2 số nguyên dương ~1 \le n, m \le 2 \times 10^5~.
• Dòng thứ 2 gồm ~n~ số nguyên dương ~1 \le a_i \le 10^9~.
• Dong thứ 3 gồm ~n~ số nguyên dương ~1 \le b_j \le 10^9~.

Output

• In ra ~m~ số nguyên tương ứng với đáp án.

Sample Test

Input:

4 4
1 25 121 169
1 2 7 23

Output:

2 3 8 24