#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
#define iosf ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int maxn = 3030;
constexpr int mod = 1000000007;
int n, m, nums[maxn];

template<typename T>
inline T nxt() {
	T x;
	cin >> x;
	return x;
}
//template<typename T>
//T gcd(T a, T b) {
//	return b == 0 ? a : gcd(b, a % b);
//}
LL gcd(LL x, LL	y) {
	return y == 0 ? x : gcd(y, x % y);
}
// 快速GCD
template<typename T>
T qGCD(T a, T b)
{
	if (a == 0) return b;
	if (b == 0) return a;
	if (!(a & 1) && !(b & 1)) // a % 2 == 0 && b % 2 == 0;
		return qGCD(a >> 1, b >> 1) << 1;
	else if (!(b & 1))
		return qGCD(a, b >> 1);
	else if (!(a & 1))
		return qGCD(a >> 1, b);
	else
		return qGCD(abs(a - b), min(a, b));
}

void solve() {
	vector<LL> a(n), b(m);
	generate(all(a), nxt<LL>);
	generate(all(b), nxt<LL>);

	LL g = 0;
	for (int i = 1; i < n; ++i) {
		g = qGCD<LL>(g, abs(a[i] - a[0]));
	}
	for (int i = 0; i < m; ++i) {
		if (i != 0) cout << " ";
		cout << qGCD<LL>(g, a[0] + b[i]);
	}
	cout << endl;
	printf("\n");
}

int main() 
{
	iosf;
#ifdef DEBUG
	freopen("in.txt", "r", stdin);
#endif
	cin >> n >> m;
	solve();
	return 0;
}
### Prompt

In Cpp, your task is to solve the following problem:

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
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all((x))); (x).resize(unique(all((x))) - (x).begin())
#define iosf ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using LL = long long;
using pii = pair<int, int>;

const int maxn = 3030;
constexpr int mod = 1000000007;
int n, m, nums[maxn];

template<typename T>
inline T nxt() {
	T x;
	cin >> x;
	return x;
}
//template<typename T>
//T gcd(T a, T b) {
//	return b == 0 ? a : gcd(b, a % b);
//}
LL gcd(LL x, LL	y) {
	return y == 0 ? x : gcd(y, x % y);
}
// 快速GCD
template<typename T>
T qGCD(T a, T b)
{
	if (a == 0) return b;
	if (b == 0) return a;
	if (!(a & 1) && !(b & 1)) // a % 2 == 0 && b % 2 == 0;
		return qGCD(a >> 1, b >> 1) << 1;
	else if (!(b & 1))
		return qGCD(a, b >> 1);
	else if (!(a & 1))
		return qGCD(a >> 1, b);
	else
		return qGCD(abs(a - b), min(a, b));
}

void solve() {
	vector<LL> a(n), b(m);
	generate(all(a), nxt<LL>);
	generate(all(b), nxt<LL>);

	LL g = 0;
	for (int i = 1; i < n; ++i) {
		g = qGCD<LL>(g, abs(a[i] - a[0]));
	}
	for (int i = 0; i < m; ++i) {
		if (i != 0) cout << " ";
		cout << qGCD<LL>(g, a[0] + b[i]);
	}
	cout << endl;
	printf("\n");
}

int main() 
{
	iosf;
#ifdef DEBUG
	freopen("in.txt", "r", stdin);
#endif
	cin >> n >> m;
	solve();
	return 0;
}
```