Manager of HackerX company is having big trouble. Workers are very unhappy with the way salary is given to them. They want every worker to have the same salary, otherwise they will go on a strike.
Their current salaries are denoted by a sequence of N integers: A1, A2, A3 ... AN . Manager has decided to take action and make their salaries equal. He uses the following process until all salaries are equal. This method is called normalization:
a) Select any two different values from A.
b) Replace larger value with the difference of the two. Difference of two positive integers Band C is defined as |B-C|.
He knows that the final value will always be unique.
Now, Q queries are given. In each query you are given an integer K. K is the amount to be added to everyone's salary as bonus, before the normalization.
Now, Q queries are given. In each query you are given an integer K. K is the amount to be added to everyone's salary as bonus, before the normalization.
Input Format
First line contains, N and Q, the number of employees and the number of queries. Next line contains N space seperated positive integers denoting the array A. Next Q lines contain queries. Each query consists of one integer per line denoting K.
First line contains, N and Q, the number of employees and the number of queries. Next line contains N space seperated positive integers denoting the array A. Next Q lines contain queries. Each query consists of one integer per line denoting K.
Output Format
For each query, print the normalized salary (which is same for everyone in the end) in one line.
For each query, print the normalized salary (which is same for everyone in the end) in one line.
Constraints
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ A[i] ≤ 1014
0 ≤ K ≤ 109
1 ≤ N ≤ 105
1 ≤ Q ≤ 105
1 ≤ A[i] ≤ 1014
0 ≤ K ≤ 109
Sample Input
4 2
9 12 3 6
0
3
Sample Output
3
3
Explanation
for sample input:
If 0 is added to every element of array A, it will remain same.
One way to normalise A is this:
1. Picking 12 and 3 gives: 9 9 3 6
2. Picking 3 and 6 gives: 9 9 3 3
3. Picking 9 and 3 gives: 6 9 3 3
4. Picking 9 and 3 gives: 6 6 3 3
5. Picking 6 and 3 gives: 3 6 3 3
6. Picking 6 and 3 gives: 3 3 3 3
for sample input:
If 0 is added to every element of array A, it will remain same.
One way to normalise A is this:
1. Picking 12 and 3 gives: 9 9 3 6
2. Picking 3 and 6 gives: 9 9 3 3
3. Picking 9 and 3 gives: 6 9 3 3
4. Picking 9 and 3 gives: 6 6 3 3
5. Picking 6 and 3 gives: 3 6 3 3
6. Picking 6 and 3 gives: 3 3 3 3
For the salaries A1, A2, ..., An (assume sorted), the answer is gcd(A1, A2, ..., An).
If we add K to all, the answer is: gcd(A1+K, A2+K, A3+K, ..., An+K)
= gcd(A1+K, A2+K-(A1+K), A3+K-(A1+K)..., An+K-(A1+K))
= gcd(A1+K, A2 - A1, A3 - A1..., An-A1)
= gcd(A1+K, G)
= gcd(A1+K, A2+K-(A1+K), A3+K-(A1+K)..., An+K-(A1+K))
= gcd(A1+K, A2 - A1, A3 - A1..., An-A1)
= gcd(A1+K, G)
where G = gcd(A2 - A1, A3-A1..., An-A1) (precalculated).
#include<bits/stdc++.h>
using namespace std;
struct _ { ios_base::Init i; _() { cin.sync_with_stdio(0); cin.tie(0); } } _;
const int N = 100006;
long long a[N];
long long gcd(long long a, long long b)
{
if(a < 0) a = -a; if(b < 0) b = -b;
return b ? gcd(b, a % b) : a;
}
int main()
{
int n, q; cin >> n >> q;
long long temp;
assert (n<=100000 && n>=1 && q<=100000 && q>=1);
for(int i = 0; i < n; ++i) {
cin >> temp;
assert (temp<=100000000000000L && temp>=0);
a[i] = temp;
}
long long d = 0;
for(int i = 0; i < n; ++i)
d = gcd(d, a[i] - a[1]);
while(q--)
{
int k; cin >> k;
assert (k>=0 && k<=1000000000);
cout << gcd(d, a[0] + k) << '\n';
}
return 0;
}
