#include <bits/stdc++.h>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define sz(c) (int)c.size()
#define fr first
#define ll long long 
#define ull unsigned long long 
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi(i,a,n) for(int i=a ; i<n ; i++)
#define fd(i,n,a) for(int i=n-1 ; i>=a ; i--)
#define r0 return 0;
#define ln "\n"
#define INF (int)1e15
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ull gcd(ull a,ull b){
	if(a==0) return b;
	if(b==0) return a;
	if(a>b) return gcd(b,a%b);
	else return gcd(b%a,a);
}
bool ispr(ull n){
	// if(n==1) return 0;
	for(ull i=2;i*i<=n;i++){
		if(n%i==0) return 0;
	}
	return 1;
}
void solve(){
	ll n,m;cin>>n>>m;
	vector<ll>a(n),b(m);
	fi(i,0,n) cin>>a[i];
	fi(i,0,m) cin>>b[i];
	if(n==1){
		fi(i,0,m) cout<<a[0]+b[i]<<" ";
		cout<<"\n";
		return ;
	}
	ll ans=a[1]-a[0];
	fi(i,2,n){
		ans=gcd(ans,a[i]-a[0]);
	}
	fi(i,0,m){
		cout<<gcd(ans,a[0]+b[i])<<" ";
	}
	cout<<"\n";
}
int main(){
    fast
    // ll t;cin>>t;
    ll t=1;
    while(t--) solve();
    r0;
}
### 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>
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define sz(c) (int)c.size()
#define fr first
#define ll long long 
#define ull unsigned long long 
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define fi(i,a,n) for(int i=a ; i<n ; i++)
#define fd(i,n,a) for(int i=n-1 ; i>=a ; i--)
#define r0 return 0;
#define ln "\n"
#define INF (int)1e15
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
ull gcd(ull a,ull b){
	if(a==0) return b;
	if(b==0) return a;
	if(a>b) return gcd(b,a%b);
	else return gcd(b%a,a);
}
bool ispr(ull n){
	// if(n==1) return 0;
	for(ull i=2;i*i<=n;i++){
		if(n%i==0) return 0;
	}
	return 1;
}
void solve(){
	ll n,m;cin>>n>>m;
	vector<ll>a(n),b(m);
	fi(i,0,n) cin>>a[i];
	fi(i,0,m) cin>>b[i];
	if(n==1){
		fi(i,0,m) cout<<a[0]+b[i]<<" ";
		cout<<"\n";
		return ;
	}
	ll ans=a[1]-a[0];
	fi(i,2,n){
		ans=gcd(ans,a[i]-a[0]);
	}
	fi(i,0,m){
		cout<<gcd(ans,a[0]+b[i])<<" ";
	}
	cout<<"\n";
}
int main(){
    fast
    // ll t;cin>>t;
    ll t=1;
    while(t--) solve();
    r0;
}
```