Cho số nguyên dương ~ n, k ~ và dãy số nguyên dương ~ a_1, a_2, …, a_n ~. Jerry muốn san bằng dãy số ~ a_1 + k, a_2 + k, …, a_{i-1} + k, a_n + k ~ bằng cách thực hiện nhiều lần các bước sau:

1. Chọn 2 số khác nhau trong dãy, gọi giá trị hai số đó là ~ x, y ~
2. Thay giá trị số lớn bằng ~ |x - y| ~

Các bước trên được thực hiện cho đến khi tất cả các số trong dãy có giá trị như nhau.

Ví dụ với dãy số ~ (3, 12, 6~ và ~k = 3 ~ thì Jerry sẽ thực hiện trên dãy số ~ (3+3, 12+3, 6+3 ) ~ như sau: ~ (6, 15, 9 ) ~ → chọn số ~ 6 ~ và ~ 15 ~ ~ → ~ ~ ( 6, 9, 9 ) ~ ~ → ~ chọn số ~ 6 ~ và ~ 9 ~ ~ → ~ ~ (6, 3, 9) ~ ~ → ~ chọn số ~ 3 ~ và ~ 9 ~ ~ → ~ ~ ( 6, 3, 6) ~ ~ → ~ chọn số ~ 6 ~ và ~ 3 ~ ~ → ~ ~ ( 3, 3, 6) ~ ~ → ~ chọn số ~ 6 ~ và ~ 3 ~ ~ → ~ ~ (3, 3, 3) ~. Vậy kết quả là ~ 3 ~

Dữ liệu vào

• Dòng đầu tiên ghi hai số nguyên dương ~ n,q ~ ~ (1 ≤ n, q ≤ 10^5) ~ lần lượt cho biết số lượng phần tử dãy số và số lượng truy vấn.
• Dòng thứ 2 ghi lần lượt các số ~ a_1, a_2, …, a_n ~ ~ (1 ≤ a_i ≤ 10^{14}) ~
• ~ q ~ dòng tiếp theo, mỗi dòng ghi một số nguyên dương ~ k ~ ~ ( 0 ≤ k ≤ 10^9) ~

Kết quả

• Với mỗi truy vấn, in ra giá trị một phần tử của dãy ~ a_1 + k, a_2 + k,…, a_{i-1}+k, a_n + k ~ sau khi thực hiện san bằng. Mỗi truy vấn in kết quả trên một dòng.

Ví dụ:

Input 1

3 2
3 12 6
0
3 

Output 1

3
3