#include<bits/stdc++.h>
//#include<bits/extc++.h>
#define ll long long
#define int long long
//#define int __int128
//#define int __uint128_t
#define ull unsigned long long
#define MMST(x,y) memset(x,y,sizeof(x))

using namespace std;
//using namespace _gnu_pbds;

const int INF=0x3f3f3f3f;

int read()
{
	char c;
	int num,f=1;
	while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;
	num=(int)(c-'0');
	while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');
	return num*f;
}
void prt(int x)
{
 	if(x<0)
 	{
 		putchar('-');
 		x=-x;
	 }
	 if(x>9)prt(x/10);
	 putchar(x%10+'0');
}

int n,m;
int a[200010],b[200010]; 
int gcd(int a,int b)
{
	if(b==0)return a;
	else return gcd(b,a%b);
}
int ans;
void work()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+1+n);
	for(int i=2;i<=n;i++)
	{
		ans=gcd(ans,a[i]-a[1]);
	}
	for(int i=1;i<=m;i++)
	{
		b[i]=read();
		prt(gcd(ans,a[1]+b[i]));
		printf(" ");
	}
	return;
}

signed main()
{
	int T=1;//read();
	for(int Case=1;Case<=T;Case++)
	{
		//printf("Case #%d: ",Case);
		work();
	}
	return 0;
}


### Prompt

Your task is to create 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>
//#include<bits/extc++.h>
#define ll long long
#define int long long
//#define int __int128
//#define int __uint128_t
#define ull unsigned long long
#define MMST(x,y) memset(x,y,sizeof(x))

using namespace std;
//using namespace _gnu_pbds;

const int INF=0x3f3f3f3f;

int read()
{
	char c;
	int num,f=1;
	while(c=(char)getchar(),!isdigit(c))if(c=='-')f=-1;
	num=(int)(c-'0');
	while(c=(char)getchar(),isdigit(c))num=num*10+(int)(c-'0');
	return num*f;
}
void prt(int x)
{
 	if(x<0)
 	{
 		putchar('-');
 		x=-x;
	 }
	 if(x>9)prt(x/10);
	 putchar(x%10+'0');
}

int n,m;
int a[200010],b[200010]; 
int gcd(int a,int b)
{
	if(b==0)return a;
	else return gcd(b,a%b);
}
int ans;
void work()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	sort(a+1,a+1+n);
	for(int i=2;i<=n;i++)
	{
		ans=gcd(ans,a[i]-a[1]);
	}
	for(int i=1;i<=m;i++)
	{
		b[i]=read();
		prt(gcd(ans,a[1]+b[i]));
		printf(" ");
	}
	return;
}

signed main()
{
	int T=1;//read();
	for(int Case=1;Case<=T;Case++)
	{
		//printf("Case #%d: ",Case);
		work();
	}
	return 0;
}


```