// After Seeing Editorial
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

typedef long long ll;
typedef unsigned long long int ull;
typedef long double ldb;

#define PB push_back
	
#define Fas ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

ll power(ll a,ll b){
    int result=1;
    while(b>0){
        if(b%2 == 1){
            result *= a;
        }
        a *= a;
        b /= 2;
    }
    return result;
}
//ll gcd(ll x,ll y){
//    if(x==1||y==1){
//        return 1;
//    }else if(x==0){
//        return y;
//    }else if(y==0){
//        return x;
//    }else if(( x >= y ) && (( x % y ) != 0)){
//        return gcd(x-y,y);
//    }else if(x>=y &&(x%y ==0)){
//        return y;
//    }else if(( y >= x ) && (( y % x ) != 0)){
//        return gcd(y-x,x);
//    }else if(y>=x &&((y%x)==0)){
//        return x;
//    }
//}
ll gcd(ll x,ll y){
    ll r;
    while(y!=0&&(r=x%y)!=0){
        x=y;
        y=r;
    }
    return y==0?x:y;
}
void solve(){
    ll a,b,g;
    cin>>a>>b;
    vector<ll> A(a);
    vector<ll> B(b);
    vector<ll> ans(b);
    if(a>1){
        cin>>A[0];
        for(ll i=1;i<a;i++){
            cin>>A[i];
            A[i]= abs(A[i]-A[0]);
            if(i==1){
                g=A[1];
            }else{
                g=gcd(g,A[i]);
            }
        }
        for(ll i=0;i<b;i++){
            cin>>B[i];
            ll c=abs(A[0]+B[i]);
            ans[i]=gcd(c,g);
        }
        for(auto vec:ans){
            cout<<vec<<" ";
        }
    }else{
        cin>>A[0];
        for(ll i=0;i<b;i++){
            cin>>B[i];
            cout<<A[0]+B[i]<<" ";
        }
    }
    
}

int main(){
    Fas;
//	ll t{};
//	cin>>t;
//	
//	while(t--){
		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
// After Seeing Editorial
#include <iostream>
#include <iomanip>
#include <cmath>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>

typedef long long ll;
typedef unsigned long long int ull;
typedef long double ldb;

#define PB push_back
	
#define Fas ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;

ll power(ll a,ll b){
    int result=1;
    while(b>0){
        if(b%2 == 1){
            result *= a;
        }
        a *= a;
        b /= 2;
    }
    return result;
}
//ll gcd(ll x,ll y){
//    if(x==1||y==1){
//        return 1;
//    }else if(x==0){
//        return y;
//    }else if(y==0){
//        return x;
//    }else if(( x >= y ) && (( x % y ) != 0)){
//        return gcd(x-y,y);
//    }else if(x>=y &&(x%y ==0)){
//        return y;
//    }else if(( y >= x ) && (( y % x ) != 0)){
//        return gcd(y-x,x);
//    }else if(y>=x &&((y%x)==0)){
//        return x;
//    }
//}
ll gcd(ll x,ll y){
    ll r;
    while(y!=0&&(r=x%y)!=0){
        x=y;
        y=r;
    }
    return y==0?x:y;
}
void solve(){
    ll a,b,g;
    cin>>a>>b;
    vector<ll> A(a);
    vector<ll> B(b);
    vector<ll> ans(b);
    if(a>1){
        cin>>A[0];
        for(ll i=1;i<a;i++){
            cin>>A[i];
            A[i]= abs(A[i]-A[0]);
            if(i==1){
                g=A[1];
            }else{
                g=gcd(g,A[i]);
            }
        }
        for(ll i=0;i<b;i++){
            cin>>B[i];
            ll c=abs(A[0]+B[i]);
            ans[i]=gcd(c,g);
        }
        for(auto vec:ans){
            cout<<vec<<" ";
        }
    }else{
        cin>>A[0];
        for(ll i=0;i<b;i++){
            cin>>B[i];
            cout<<A[0]+B[i]<<" ";
        }
    }
    
}

int main(){
    Fas;
//	ll t{};
//	cin>>t;
//	
//	while(t--){
		solve();
//	}
    
	return 0;
}
```