#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct smallnode{
smallnode *lc,*rc;
long long val;
smallnode(){
lc=rc=nullptr;
val=0;
}
};
struct bignode{
bignode *lc,*rc;
smallnode *down;
long long val;
bignode(){
lc=rc=nullptr;
down=nullptr;
val=0;
}
};
bignode *root;
long long gcd(long long a,long long b){
while (b) b^=a^=b^=a%=b;
return a;
}
int n,m;
void init(int R,int C){
root=new bignode;
n=R;
m=C;
}
long long queryY(smallnode *id,int tlY,int trY,int lY,int rY){
if (!id||lY>rY) return 0ll;
if (lY<=tlY&&trY<=rY) return id->val;
int tmY=(tlY+trY)/2;
long long lans=(id->lc?queryY(id->lc,tlY,tmY,lY,min(rY,tmY)):0ll);
long long rans=(id->rc?queryY(id->rc,tmY+1,trY,max(lY,tmY+1),rY):0ll);
return gcd(lans,rans);
}
long long queryX(bignode *id,int tlX,int trX,int lX,int rX,int lY,int rY){
if (!id||lX>rX) return 0ll;
if (lX<=tlX&&trX<=rX) return queryY(id->down,1,m,lY,rY);
int tmX=(tlX+trX)/2;
long long lans=(id->lc?queryX(id->lc,tlX,tmX,lX,min(rX,tmX),lY,rY):0ll);
long long rans=(id->rc?queryX(id->rc,tmX+1,trX,max(lX,tmX+1),rX,lY,rY):0ll);
return gcd(lans,rans);
}
void updateY(smallnode *id,int tlY,int trY,int yp,long long Val){
if (!id) return;
if (tlY==trY){
id->val=Val;
return;
}
int tmY=(tlY+trY)/2;
if (yp<=tmY){
if (!id->lc) id->lc=new smallnode;
updateY(id->lc,tlY,tmY,yp,Val);
} else {
if (!id->rc) id->rc=new smallnode;
updateY(id->rc,tmY+1,trY,yp,Val);
}
long long lans=(id->lc?id->lc->val:0ll);
long long rans=(id->rc?id->rc->val:0ll);
id->val=gcd(lans,rans);
}
void updateX(bignode *id,int tlX,int trX,int xp,int yp,long long Val){
if (!id->down) id->down=new smallnode;
if (tlX==trX){
updateY(id->down,1,m,yp,Val);
return;
}
int tmX=(tlX+trX)/2;
if (xp<=tmX){
if (!id->lc) id->lc=new bignode;
updateX(id->lc,tlX,tmX,xp,yp,Val);
} else {
if (!id->rc) id->rc=new bignode;
updateX(id->rc,tmX+1,trX,xp,yp,Val);
}
long long lans=(id->lc?queryY(id->lc->down,1,m,yp,yp):0ll);
long long rans=(id->rc?queryY(id->rc->down,1,m,yp,yp):0ll);
updateY(id->down,1,m,yp,gcd(lans,rans));
}
void update(int P,int Q,long long K){
updateX(root,1,n,P+1,Q+1,K);
}
long long calculate(int P,int Q,int U,int V){
return queryX(root,1,n,P+1,U+1,Q+1,V+1);
}
