Trivial? Solve It!

You are given an array of integers $a_1,a_2,\dots ,a_n$. Your task is to process $q$ queries:

• add an integer $x$ to all elements of the array.

After each query, output the greatest common divisor of all elements of the array.

Input

The first line contains two integers $n$, $q$ ($1\le n,q\le 2\cdot 10^5$) — the size of the array and the number of queries, respectively.

The second line contains $n$ integers $a_1,\dots ,a_n$ ($1\le a_i\le 10^9$) — the elements of the array $a$.

Each of the next $q$ lines contains one integer $x$ ($1\le x\le 10^9$).

Output

Output $q$ numbers — the greatest common divisor of the elements of the array after each addition.

Examples

Note

After the first query $a=[2,10,18]$ because $1$ was added to each element. The greatest common divisor in it is $2$.

After the second query $a=[4,12,20]$ because $2$ was added to each element. The greatest common divisor in it is $4$.

After the third query $a=[8,16,24]$ because $4$ was added to each element. The greatest common divisor in it is $8$.

Scoring

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.

1. ($5$ points): $a_1=a_2=\cdots =a_n$;

2. ($15$ points): $n,q\le 1000$;

3. ($40$ points): the number of different elements among $a_1,\dots ,a_n$ is no more than $100$;

4. ($40$ points): without additional constraints.