Trivial? Solve It!#14

Trivial? Solve It!

2 seconds
256 megabytes
Medium

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

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

Input

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

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

Examples

Example

Loading
Loading

Note

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 .

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. ( points): a_1=a_2=\dots=a_n;

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

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

  4. ( points): without additional constraints.