#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define all(v) (v).begin(), (v).end()
#define endl "\n"

ll mod=1e9+7;
void prime(ll a,vector<ll> &v){
    for(ll i=2ll;i*i<=a;i++){
        if(a%i==0ll)v.push_back(i);
        while(a%i==0ll){
            a=a/i;
        }
    }
    if(a>1ll)
    v.push_back(a);
}
bool isprime(ll a){
    for(ll i=2;i*i<=a;i++)
    if(a%i==0)return false;
    return true;
}
ll expmod(ll a,ll b) {
	if(b == 1) return a;
	if(b == 0) return 1;
	ll m1 = expmod(a,b/2)%mod;
	if(b%2) return ((m1*m1)%mod*a%mod)%mod;
	return (m1*m1)%mod;
}
ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}

// ll dp[2005][2005];
// ll nCr(ll n, ll r)
// {
// if(n<r)return 0ll;
// if(n==r) return dp[n][r] = 1ll;
// if(r==0) return dp[n][r] = 1ll;
// if(r==1) return dp[n][r] = n;
// if(dp[n][r]!=-1) return dp[n][r];
// dp[n][r] = nCr(n-1,r)%mod + nCr(n-1,r-1)%mod;
// dp[n][r]%=mod;
// return dp[n][r];
// }
struct myComp { 
    constexpr bool operator()( 
        pair<int,pair<int, int>> const& a, 
        pair<int,pair<int, int>> const& b) 
        const noexcept 
    { 
        if(a.first<b.first)return true;
        if(a.first>b.first)return false;
        return a.second.first>b.second.first;
    } 
};
typedef pair<ll,ll> pll; 
typedef pair<int,int> pii;
typedef pair<ll,int> pli; 
typedef pair<int,ll> pil; 
class compare{
public:
  bool operator()(pair<int, ll> &p, pair<int, ll> &q)
  {
    return p.second >= q.second;
  }
};
 
ll bs1(ll a[],ll n,ll x){
    ll anss=-1;
    ll l=0;ll h=n-1;
    while(l<=h){
        ll mid=l+(h-l)/2;
        if(a[mid]<=x){
           // if(a[mid]==x)
            anss=mid;
            l=mid+1;
        }
        else
        h=mid-1;
    }
    return anss;
}
ll bs2(ll a[],ll n,ll x){
    ll anss=-1;
    ll l=0;ll h=n-1;
    while(l<=h){
        ll mid=l+(h-l)/2;
        //cout<<"*"<<a[mid]<<"* ";
        if(a[mid]>x){
            anss=mid;h=mid-1;
        }
        else
        l=mid+1;
    }
    return anss;
}
//<--------********-------->
int bs3(vector<int> a,int x){
    int anss=-1;
    int l=0;int h=a.size()-1;
    while(l<=h){
        int mid=l+(h-l)/2;
        if(a[mid]<=x){
           // if(a[mid]==x)
            anss=mid;
            l=mid+1;
        }
        else
        h=mid-1;
    }
    return anss;
}

//<--------********-------->
 //make all possible test cases
 //check for log long i.e int out of bound
 //make most out of constraints
 // check if present state is dependent on past states and if how construct step by step
 // sometimes it is useful to find no of wrong answer thus ans=total-negation.

// bool vis[509][509];
// int dx[4]={0,0,-1,1};
// int dy[4]={-1,1,0,0};
// inline bool good(int x,int y,int n,int m){
// 	return x>=0 && x<n && y>=0 && y<m;
// }


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int test;
    test=1;
    //cin>>test;
    while(test--){
       int n,m;
       cin>>n>>m;
       ll a[n];ll b[m];
       for(int i=0;i<n;i++)cin>>a[i];
       for(int i=0;i<m;i++)cin>>b[i];
       sort(a,a+n);
       ll g=0;
       for(int i=1;i<n;i++){
           g=gcd(g,a[i]-a[0]);
       }
       for(int i=0;i<m;i++){
           ll t=gcd(a[0]+b[i],g);
           cout<<t<<" ";
       }
       cout<<endl;
    }
}
     
### Prompt

Your challenge is to write a Cpp solution to 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
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define all(v) (v).begin(), (v).end()
#define endl "\n"

ll mod=1e9+7;
void prime(ll a,vector<ll> &v){
    for(ll i=2ll;i*i<=a;i++){
        if(a%i==0ll)v.push_back(i);
        while(a%i==0ll){
            a=a/i;
        }
    }
    if(a>1ll)
    v.push_back(a);
}
bool isprime(ll a){
    for(ll i=2;i*i<=a;i++)
    if(a%i==0)return false;
    return true;
}
ll expmod(ll a,ll b) {
	if(b == 1) return a;
	if(b == 0) return 1;
	ll m1 = expmod(a,b/2)%mod;
	if(b%2) return ((m1*m1)%mod*a%mod)%mod;
	return (m1*m1)%mod;
}
ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return (a*b)/gcd(a,b);
}

// ll dp[2005][2005];
// ll nCr(ll n, ll r)
// {
// if(n<r)return 0ll;
// if(n==r) return dp[n][r] = 1ll;
// if(r==0) return dp[n][r] = 1ll;
// if(r==1) return dp[n][r] = n;
// if(dp[n][r]!=-1) return dp[n][r];
// dp[n][r] = nCr(n-1,r)%mod + nCr(n-1,r-1)%mod;
// dp[n][r]%=mod;
// return dp[n][r];
// }
struct myComp { 
    constexpr bool operator()( 
        pair<int,pair<int, int>> const& a, 
        pair<int,pair<int, int>> const& b) 
        const noexcept 
    { 
        if(a.first<b.first)return true;
        if(a.first>b.first)return false;
        return a.second.first>b.second.first;
    } 
};
typedef pair<ll,ll> pll; 
typedef pair<int,int> pii;
typedef pair<ll,int> pli; 
typedef pair<int,ll> pil; 
class compare{
public:
  bool operator()(pair<int, ll> &p, pair<int, ll> &q)
  {
    return p.second >= q.second;
  }
};
 
ll bs1(ll a[],ll n,ll x){
    ll anss=-1;
    ll l=0;ll h=n-1;
    while(l<=h){
        ll mid=l+(h-l)/2;
        if(a[mid]<=x){
           // if(a[mid]==x)
            anss=mid;
            l=mid+1;
        }
        else
        h=mid-1;
    }
    return anss;
}
ll bs2(ll a[],ll n,ll x){
    ll anss=-1;
    ll l=0;ll h=n-1;
    while(l<=h){
        ll mid=l+(h-l)/2;
        //cout<<"*"<<a[mid]<<"* ";
        if(a[mid]>x){
            anss=mid;h=mid-1;
        }
        else
        l=mid+1;
    }
    return anss;
}
//<--------********-------->
int bs3(vector<int> a,int x){
    int anss=-1;
    int l=0;int h=a.size()-1;
    while(l<=h){
        int mid=l+(h-l)/2;
        if(a[mid]<=x){
           // if(a[mid]==x)
            anss=mid;
            l=mid+1;
        }
        else
        h=mid-1;
    }
    return anss;
}

//<--------********-------->
 //make all possible test cases
 //check for log long i.e int out of bound
 //make most out of constraints
 // check if present state is dependent on past states and if how construct step by step
 // sometimes it is useful to find no of wrong answer thus ans=total-negation.

// bool vis[509][509];
// int dx[4]={0,0,-1,1};
// int dy[4]={-1,1,0,0};
// inline bool good(int x,int y,int n,int m){
// 	return x>=0 && x<n && y>=0 && y<m;
// }


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int test;
    test=1;
    //cin>>test;
    while(test--){
       int n,m;
       cin>>n>>m;
       ll a[n];ll b[m];
       for(int i=0;i<n;i++)cin>>a[i];
       for(int i=0;i<m;i++)cin>>b[i];
       sort(a,a+n);
       ll g=0;
       for(int i=1;i<n;i++){
           g=gcd(g,a[i]-a[0]);
       }
       for(int i=0;i<m;i++){
           ll t=gcd(a[0]+b[i],g);
           cout<<t<<" ";
       }
       cout<<endl;
    }
}
     
```