#include <bits/stdc++.h>

template <typename T> inline void rd(T& x) {
	int si = 1; char c = getchar(); x = 0;
	while(!isdigit(c)) si = c == '-' ? -1 : si, c = getchar();
	while(isdigit(c)) x = x * 10 + c - 48, c = getchar();
	x *= si;
}
template <typename T, typename... Args>
inline void rd(T& x, Args&... args) { rd(x); rd(args...); }
#define fi first
#define se second
#define mkp std::make_pair
typedef long long ll;
typedef double ff;
typedef std::pair <int, int> pii;
const int kN = 5e5 + 5, kInf = 0x3f3f3f3f;
const ll kMod = 998244353, kInfLL = 0x3f3f3f3f3f3f3f3fLL;

int n, m; ll A[kN], B[kN];
ll Gcd(ll a, ll b) { return b ? Gcd(b, a % b) : a; }

int main() { 
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int T = 1; //rd(T);
	while(T--) {
		rd(n, m);
		for(int i = 1; i <= n; ++i) rd(A[i]);
		std::sort(A + 1, A + n + 1);
		for(int i = 1; i <= m; ++i) rd(B[i]);
		if(n == 1) {
			for(int j = 1; j <= m; ++j) {
				printf("%lld ", A[1] + B[j]);
			}
			printf("\n");
			return 0;
		}
		ll g = A[n] - A[n - 1];
		for(int i = n - 1; i > 1; --i) g = Gcd(g, A[i] - A[i - 1]);
		for(int i = 1; i <= m; ++i) {
			printf("%lld ", Gcd(g, A[1] + B[i]));
		}
		printf("\n");
	} return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

You are given two positive integer sequences a_1, …, a_n and b_1, …, b_m. For each j = 1, …, m find the greatest common divisor of a_1 + b_j, …, a_n + b_j.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 2 ⋅ 10^5).

The second line contains n integers a_1, …, a_n (1 ≤ a_i ≤ 10^{18}).

The third line contains m integers b_1, …, b_m (1 ≤ b_j ≤ 10^{18}).

Output

Print m integers. The j-th of them should be equal to GCD(a_1 + b_j, …, a_n + b_j).

Example

Input


4 4
1 25 121 169
1 2 7 23


Output


2 3 8 24

### Response

```cpp
#include <bits/stdc++.h>

template <typename T> inline void rd(T& x) {
	int si = 1; char c = getchar(); x = 0;
	while(!isdigit(c)) si = c == '-' ? -1 : si, c = getchar();
	while(isdigit(c)) x = x * 10 + c - 48, c = getchar();
	x *= si;
}
template <typename T, typename... Args>
inline void rd(T& x, Args&... args) { rd(x); rd(args...); }
#define fi first
#define se second
#define mkp std::make_pair
typedef long long ll;
typedef double ff;
typedef std::pair <int, int> pii;
const int kN = 5e5 + 5, kInf = 0x3f3f3f3f;
const ll kMod = 998244353, kInfLL = 0x3f3f3f3f3f3f3f3fLL;

int n, m; ll A[kN], B[kN];
ll Gcd(ll a, ll b) { return b ? Gcd(b, a % b) : a; }

int main() { 
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
	freopen("a.out", "w", stdout);
#endif
	int T = 1; //rd(T);
	while(T--) {
		rd(n, m);
		for(int i = 1; i <= n; ++i) rd(A[i]);
		std::sort(A + 1, A + n + 1);
		for(int i = 1; i <= m; ++i) rd(B[i]);
		if(n == 1) {
			for(int j = 1; j <= m; ++j) {
				printf("%lld ", A[1] + B[j]);
			}
			printf("\n");
			return 0;
		}
		ll g = A[n] - A[n - 1];
		for(int i = n - 1; i > 1; --i) g = Gcd(g, A[i] - A[i - 1]);
		for(int i = 1; i <= m; ++i) {
			printf("%lld ", Gcd(g, A[1] + B[i]));
		}
		printf("\n");
	} return 0;
}
```