#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/detail/standard_policies.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// common
#define endl     "\n"
#define M_PI     3.14159265358979323846

// fast input output
#define fast_io  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

// fixed float field
#define fix_prec cout.setf( std::ios::fixed, std:: ios::floatfield ); cout.precision(9);

// vector
#define pb      push_back
#define pf      push_front
#define eb      emplace_back        

// pair
#define mp       make_pair
#define F        first
#define S        second

// sort
#define all(x)   x.begin(),x.end()
#define rall(x)  x.rbegin(),x.rend()

// bound
#define lb       lower_bound
#define ub       upper_bound

using namespace std;
//using namespace __gnu_pbds;

//typedef tree < int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update > ordered_set;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef vector<int> vi;
typedef vector<lli> vlli;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<lli,lli>> vplli;
typedef pair<int,int> pii;
typedef pair<lli,lli> plli;
typedef map<int,int> mii;
typedef map<lli,lli> mlli;

// constants
lli const mod  = 1e9+7;
lli const modl = 1e18;

// helper functions
// calculate gcd
lli gcd(lli a, lli b)
{
    if (b==0)
        return a;
    return gcd(b, a%b);
}

// calculate lcm
lli lcm(lli a, lli b)
{
	return a/gcd(a,b)*b;
}

// calculate fibonacci number
lli fib(int n)
{
    lli a,b,c,i;
    a=0,b=1;
    if(n==0)
        return a;
    for(i=2;i<=n;i++)
    {
    	c=a+b;
    	a=b;
    	b=c;
    }
    return b;
}

// check if number if prime or not
bool isprime(lli n)
{
	if(n<=1)
		return false;
	else if(n==2)
		return true;
	else if(n%2==0)
		return false;
	else
	{
		int i;
		for(i=3;i*i<=n;i++)
		{
			if(n%i==0)
				return false;
		}
		return true;
	}
}

// check if number is power of 2
bool ispowerof2(lli a)
{
	return (a&&!(a&(a-1)));
}

// read from and write to text file
void readwrite()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
} 

// seive of eratosthenes
vector<lli>prime(100000+7,1);
void buildprime(lli n)
{
	lli i,j;
	prime[0]=prime[1]=0;
	for(i=2;i*i<=n;i++)
	{
		if(prime[i])
		{
			for(j=i*i;j<=n;j+=i)
				prime[j]=0;
		}
	}
}

// nCr
lli dp[1005][1005];
lli comb[1005][1005];
lli ncr(lli n,lli r)
{
	if(n==r)
		return 1;
	if(r==0)
		return 1;
	if(r==1)
		return n;
	if(dp[n][r]!=0)
		return dp[n][r];
	return dp[n][r] = (ncr(n-1,r)%mod+ncr(n-1,r-1)%mod)%mod;
}

void ncrm()
{
	comb[0][0]=1;
	for(int i=1;i<1001;i++)
	{
		comb[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			if(j==0 || j==i)
				comb[i][j]=1;
			else
				comb[i][j]=(comb[i-1][j]%mod+comb[i-1][j-1]%mod)%mod;
		}
	}
}

// binary exponentiation
lli binpowm(lli a,lli b)
{
	lli res=1;
	a%=mod;
	while(b>0)
	{
		if(b&1)
			res=((res%mod)*(a%mod))%mod;
		a=((a%mod)*(a%mod))%mod;
		b>>=1;
	}
	return res%mod;
}
 
// factorial
lli fact(lli n)
{
	lli i,res=1;
	for(i=1;i<=n;i++)
		res=((res%mod)*(i%mod))%mod;
	return res%mod;
}

void solve()
{
	lli n,m,i;
	cin>>n>>m;
	vlli a(n),b(m);
	for(i=0;i<n;i++)
		cin>>a[i];
	for(i=0;i<m;i++)
		cin>>b[i];
	if(n==1)
	{
		for(i=0;i<m;i++)
			cout<<a[0]+b[i]<<" ";
		return;
	}
	lli g=(a[1]-a[0]);
	for(i=2;i<n;i++)
		g=gcd(g,(a[i]-a[0]));
	
	for(i=0;i<m;i++)
		cout<<abs(gcd(a[0]+b[i],g))<<" ";	
}

int main()
{
  fast_io;
  fix_prec;
  //readwrite();
  int _=1;
  //cin>>_;
  while(_--)
  {
    solve();
    cout<<endl;     
  }
  return 0;	
}

### Prompt

Create a solution in Cpp for 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>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/detail/standard_policies.hpp>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// common
#define endl     "\n"
#define M_PI     3.14159265358979323846

// fast input output
#define fast_io  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

// fixed float field
#define fix_prec cout.setf( std::ios::fixed, std:: ios::floatfield ); cout.precision(9);

// vector
#define pb      push_back
#define pf      push_front
#define eb      emplace_back        

// pair
#define mp       make_pair
#define F        first
#define S        second

// sort
#define all(x)   x.begin(),x.end()
#define rall(x)  x.rbegin(),x.rend()

// bound
#define lb       lower_bound
#define ub       upper_bound

using namespace std;
//using namespace __gnu_pbds;

//typedef tree < int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update > ordered_set;
typedef long long int lli;
typedef unsigned long long int ulli;
typedef vector<int> vi;
typedef vector<lli> vlli;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<lli,lli>> vplli;
typedef pair<int,int> pii;
typedef pair<lli,lli> plli;
typedef map<int,int> mii;
typedef map<lli,lli> mlli;

// constants
lli const mod  = 1e9+7;
lli const modl = 1e18;

// helper functions
// calculate gcd
lli gcd(lli a, lli b)
{
    if (b==0)
        return a;
    return gcd(b, a%b);
}

// calculate lcm
lli lcm(lli a, lli b)
{
	return a/gcd(a,b)*b;
}

// calculate fibonacci number
lli fib(int n)
{
    lli a,b,c,i;
    a=0,b=1;
    if(n==0)
        return a;
    for(i=2;i<=n;i++)
    {
    	c=a+b;
    	a=b;
    	b=c;
    }
    return b;
}

// check if number if prime or not
bool isprime(lli n)
{
	if(n<=1)
		return false;
	else if(n==2)
		return true;
	else if(n%2==0)
		return false;
	else
	{
		int i;
		for(i=3;i*i<=n;i++)
		{
			if(n%i==0)
				return false;
		}
		return true;
	}
}

// check if number is power of 2
bool ispowerof2(lli a)
{
	return (a&&!(a&(a-1)));
}

// read from and write to text file
void readwrite()
{
	#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
	#endif
} 

// seive of eratosthenes
vector<lli>prime(100000+7,1);
void buildprime(lli n)
{
	lli i,j;
	prime[0]=prime[1]=0;
	for(i=2;i*i<=n;i++)
	{
		if(prime[i])
		{
			for(j=i*i;j<=n;j+=i)
				prime[j]=0;
		}
	}
}

// nCr
lli dp[1005][1005];
lli comb[1005][1005];
lli ncr(lli n,lli r)
{
	if(n==r)
		return 1;
	if(r==0)
		return 1;
	if(r==1)
		return n;
	if(dp[n][r]!=0)
		return dp[n][r];
	return dp[n][r] = (ncr(n-1,r)%mod+ncr(n-1,r-1)%mod)%mod;
}

void ncrm()
{
	comb[0][0]=1;
	for(int i=1;i<1001;i++)
	{
		comb[i][0]=1;
		for(int j=1;j<=i;j++)
		{
			if(j==0 || j==i)
				comb[i][j]=1;
			else
				comb[i][j]=(comb[i-1][j]%mod+comb[i-1][j-1]%mod)%mod;
		}
	}
}

// binary exponentiation
lli binpowm(lli a,lli b)
{
	lli res=1;
	a%=mod;
	while(b>0)
	{
		if(b&1)
			res=((res%mod)*(a%mod))%mod;
		a=((a%mod)*(a%mod))%mod;
		b>>=1;
	}
	return res%mod;
}
 
// factorial
lli fact(lli n)
{
	lli i,res=1;
	for(i=1;i<=n;i++)
		res=((res%mod)*(i%mod))%mod;
	return res%mod;
}

void solve()
{
	lli n,m,i;
	cin>>n>>m;
	vlli a(n),b(m);
	for(i=0;i<n;i++)
		cin>>a[i];
	for(i=0;i<m;i++)
		cin>>b[i];
	if(n==1)
	{
		for(i=0;i<m;i++)
			cout<<a[0]+b[i]<<" ";
		return;
	}
	lli g=(a[1]-a[0]);
	for(i=2;i<n;i++)
		g=gcd(g,(a[i]-a[0]));
	
	for(i=0;i<m;i++)
		cout<<abs(gcd(a[0]+b[i],g))<<" ";	
}

int main()
{
  fast_io;
  fix_prec;
  //readwrite();
  int _=1;
  //cin>>_;
  while(_--)
  {
    solve();
    cout<<endl;     
  }
  return 0;	
}

```