#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
typedef long long ll;
int n,m;
struct nodex {
int st,dr;
nodex *fiust,*fiudr;
long long val;
nodex(int stanga,int dreapta) {
st=stanga;
dr=dreapta;
val=0;
fiust=fiudr=nullptr;
}
};
struct nodey {
nodey(int stanga,int dreapta) : st(stanga), dr(dreapta), fiust(NULL), fiudr(NULL), fiux(1,m) {}
int st,dr;
nodex fiux;
nodey *fiust,*fiudr;
}*root;
ll query2(nodex *arb, int st,int dr) {
if (arb == nullptr || arb->st>dr||st>arb->dr) {
return 0;
}
if (st<=arb->st&&arb->dr<=dr) {
return arb->val;
}
int mij=(arb->st+arb->dr)/2;
return gcd2(
query2(arb->fiust,st,dr),
query2(arb->fiudr,st,dr)
);
}
ll query1(nodey *arb,int st,int dr,int p,int q,int u,int v) {
if (arb == NULL || st > u || dr<p) {
return 0;
}
if (p<=st && dr<=u) {
return query2(&arb->fiux,q,v);
}
int mij=(st+dr)/2;
return gcd2(
query1(arb->fiust,st,mij,p,q,u,v),
query1(arb->fiudr,mij+1,dr,p,q,u,v)
);
}
void init(int R, int C) {
n=R;
m=C;
root = new nodey(1,n);
}
void updatey(nodex *arb,int y,ll k) {
int st = arb->st, dr = arb->dr, mij=(st+dr)/2;
if (st==dr) {
arb->val=k;
return;
}
nodex **copil = &(y<=mij ? arb->fiust : arb->fiudr);
if (*copil == NULL) {
*copil = new nodex (y,y);
(*copil)->val = k;
} else if ((*copil)->st<=y&&y<=(*copil)->dr) {
updatey(*copil,y,k);
} else {
do {
if (y<=mij) {
dr=mij;
} else {
st=mij+1;
}
mij=(st+dr)/2;
} while ((y<=mij) == ((*copil)->dr<=mij));
nodex *nnode = new nodex(st,dr);
bool ok=(y<(*copil)->st);
if ((*copil)->dr<=mij) {
assert(!ok);
nnode->fiust = *copil;
} else {
assert(ok);
nnode->fiudr = *copil;
}
*copil=nnode;
updatey(*copil,y,k);
}
arb->val = gcd2(
arb->fiust ? arb->fiust->val : 0,
arb->fiudr ? arb->fiudr->val : 0
);
}
void updatex(nodey *arb, int st,int dr,int x,int y,long long k) {
int mij=(st+dr)/2;
if (st==dr) {
updatey(&arb->fiux,y,k);
return;
}
if (x<=mij) {
if (arb->fiust==NULL) {
arb->fiust=new nodey(st,mij);
}
updatex(arb->fiust,st,mij,x,y,k);
} else {
if (arb->fiudr==NULL) {
arb->fiudr= new nodey(mij+1,dr);
}
updatex(arb->fiudr,mij+1,dr,x,y,k);
}
ll val = gcd2(
arb->fiust ? query2(&arb->fiust->fiux,y,y) : 0,
arb->fiudr ? query2(&arb->fiudr->fiux,y,y) : 0
);
updatey(&arb->fiux,y,val);
}
void update(int P, int Q, long long K) {
P++;
Q++;
updatex(root,1,n,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
P++;
Q++;
U++;
V++;
return query1(root,1,n,P,Q,U,V);
}
