【数论】【差分】Row GCD

难了老子一天
超
下面有玄学
期待大佬解答

Description

You are given two positive integer sequences a1.....an,b1......bn
. For each j = 1,…,m find the greatest common divisor of a1+bj,……,an+bj

更相减损术是出自《九章算术》的一种求最大公约数的算法，它原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

gcd(x,y)=gcd(x,y-x)
证明：https://baike.baidu.com/item/更相减损术/449183?fromtitle=更相减损法&fromid=10277459&fr=aladdin

此结论可用数学归纳法推广到一般，该性质对多个整数都成立。
即：gcd(x,y,z,...)=gcd(x,y-x,z-y,...)（x>=y>=z）。
直观证明：
对于gcd(x,y,z)=gcd(x,y-x,z-y)：
gcd(x,y,z)
=gcd(x,gcd(y,z))
=gcd(x,gcd(y,z-y))
=gcd(x,y,z-y)
=gcd(gcd(x,y),z-y)
=gcd(gcd(x,y-x),z-y)
=gcd(x,y-x,z-y)。
更多项依次类推。

所以！
gcd(a[1]+b[j],a[2]+b[j],……,a[n]+b[j])=gcd(a[1]+b[j],gcd(a[2]-a[1],……,a[n]-a[n-1]))
我们只用处理出来gcd(a[2]-a[1],……,a[n]-a[n-1])就可以直接搞出来答案
这能省多少时间！

Input

The first line contains two integers n and m (2*10^5)

The second line contains n integers <=10^18 .

The third line contains m integers <=10^18 .

Output

Print mm integers. The jj-th of them should be equal to GCD（a1+bj,……,an+bj).

Example

Input

4 4
1 25 121 169
1 2 7 23

Output

2 3 8 24

注意：
1.a[2]-a[1]是div[2]
2.gcd(a[2]-a[1],……,a[n]-a[n-1])能计算的条件是每一项都大于0啊
意思是要先sort(a+1,a+n+1);

#include
#include
#include
using namespace std;
long long gcd(long long x,long long y){
    return y?gcd(y,x%y):x;
}
int main(){
    int n,m;
    cin>>n>>m;
    long long a[300000],div[300000];
    memset(a,0,sizeof(a));
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a,a+n+1);
    for(int i=1;i<=n;i++){
        div[i]=a[i]-a[i-1];
    }
    long long GCD=div[2];
    for(int i=2;i<=n;i++){//这里玄学的很
        GCD=gcd(GCD,div[i]);//正序迭代GCD就行，逆序迭代GCD就不行
    }
    for(int i=1;i<=m;i++){
        long long tmp;
        cin>>tmp;
        cout<