#include <bits/stdc++.h>
#include "game.h"
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;
const int MAXR=1e9,MAXC=1e9;
const int MAX1=40*22000,MAX2=20*20*22000;
int root[MAX1],cl2[MAX2],cr2[MAX2],l2[MAX2],r2[MAX2];
int cl1[MAX1],cr1[MAX1],tme1,tme2,ROOT;
LL f[MAX2];
long long gcd2(long long X, long long Y) {
if(X == 0 || Y == 0) {
return X + Y;
}
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int newNode1() {
int v=++tme1;
root[tme1]=++tme2;
l2[tme2]=0; r2[tme2]=MAXC-1;
return v;
}
int newNode2(int l,int r) {
int v=++tme2;
l2[v]=l; r2[v]=r;
return v;
}
void init(int r,int c) {
ROOT=newNode1();
}
LL que2(int x,int l,int r) {
if(x==0||l2[x]>r||r2[x]<l)
return 0;
if(l2[x]>=l&&r2[x]<=r)
return f[x];
return gcd2(que2(cl2[x],l,r),que2(cr2[x],l,r));
}
LL que1(int x,int l,int r,int ll,int rr,int xx,int yy) {
if(l>rr||r<ll||x==0)
return 0;
if(l>=ll&&r<=rr)
return que2(root[x],xx,yy);
int md=(l+r)/2;
return gcd2(que1(cl1[x],l,md,ll,rr,xx,yy),que1(cr1[x],md+1,r,ll,rr,xx,yy));
}
void upd2(int x,int y,LL k) {
//cout<<"upd2: "<<x<<" "<<l2[x]<<" "<<r2[x]<<endl;
if(l2[x]==y&&r2[x]==y) {
f[x]=k;
return;
}
int mdo=(l2[x]+r2[x])/2;
int &v=(y<=mdo?cl2[x]:cr2[x]);
if(v==0) {
v=newNode2(y,y);
f[v]=k;
}
else if(l2[v]<=y&&r2[v]>=y)
upd2(v,y,k);
else {
//cout<<"oh no "<<l2[v]<<" "<<r2[v]<<" "<<y<<endl;
int l=l2[x],r=r2[x],md=(l2[x]+r2[x])/2,t=v;
do {
if(y<=md)
r=md;
else l=md+1;
md=(l+r)/2;
} while((y<=md)==(l2[v]<=md));
//cout<<l<<" "<<r<<endl;
int nw=newNode2(l,r);
v=nw;
if(l2[t]<=md) cl2[nw]=t;
else cr2[nw]=t;
upd2(nw,y,k);
}
f[x]=gcd2(f[cl2[x]],f[cr2[x]]);
}
void upd1(int &x,int l,int r,int ll,int y,LL k) {
if(x==0)
x=newNode1();
if(l==r) {
upd2(root[x],y,k);
return;
}
int md=(l+r)/2;
if(ll<=md)
upd1(cl1[x],l,md,ll,y,k);
else upd1(cr1[x],md+1,r,ll,y,k);
upd2(root[x],y,gcd2(que2(root[cl1[x]],y,y),que2(root[cr1[x]],y,y)));
}
void update(int x,int y,LL k) {
upd1(ROOT,0,MAXR-1,x,y,k);
}
LL calculate(int p,int q,int u,int v) {
return que1(ROOT,0,MAXR-1,p,u,q,v);
}
