Row GCD

G. Row GCD

You are given two positive integer sequences $a_1,\dots ,a_n$ and $b_1,\dots ,b_m$. For each $j=1,\dots ,m$ find the greatest common divisor of $a_1+b_j,\dots ,a_n+b_j$.

Input

The first line contains two integers $n$ and $m$ ($1\le n,m\le 2\cdot 10^5$).

The second line contains $n$ integers $a_1,\dots ,a_n$ ($1\le a_i\le 10^{18})$.

The third line contains $m$ integers $b_1,\dots ,b_m$ ($1\le b_j\le 10^{18})$.

Output

Print $m$ integers. The $j$-th of them should be equal to GCD$(a_1+b_j,\dots ,a_n+b_j)$.

Example

Input

4 4
1 25 121 169
1 2 7 23

Output

2 3 8 24

code

#include<bits/stdc++.h>
#define int long long
#define endl '\n'using namespace std;const int N = 2e5+10,INF=0x3f3f3f3f,mod=1e9+7;typedef pair<int,int> PII;int T=1;void solve(){int n,m,k;cin>>n>>m>>k; int t=0;vector<int> a(n+5,0);vector<int> b(m+5,0);for(int i=1;i<n;i++){cin>>a[i];t=__gcd(t,abs(a[i]-k));}for(int i=0;i<m;i++){cin>>b[i];cout<<__gcd(t,k+b[i])<<" ";}
}signed main(){
//	cin>>T; while(T--){solve();}return 0;
}