You are given an array of integers a_1,a_2,\dots,a_n. Your task is to process queries:
add an integer to all elements of the array.
After each query, output the greatest common divisor of all elements of the array.
The first line contains two integers , (1\le n,q\le 2\cdot 10^5) — the size of the array and the number of queries, respectively.
The second line contains integers a_1,\dots,a_n (1\le a_i\le 10^9) — the elements of the array .
Each of the next lines contains one integer (1\le x\le 10^9).
Output numbers — the greatest common divisor of the elements of the array after each addition.
Example
After the first query a=[2, 10, 18] because was added to each element. The greatest common divisor in it is .
After the second query a=[4, 12, 20] because was added to each element. The greatest common divisor in it is .
After the third query a=[8, 16, 24] because was added to each element. The greatest common divisor in it is .
In this problem, there are conditional blocks. If your solution works correctly for certain constraints, it will receive a certain number of points. Note that the evaluation is still in the testing phase.
( points): a_1=a_2=\dots=a_n;
( points): n,q\le 1000;
( points): the number of different elements among a_1,\dots,a_n is no more than ;
( points): without additional constraints.