#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct nodex{
int chl,chr,chy;
};
struct nodey{
long long val;
int chl,chr;
};
nodex treex[700000];
nodey treey[50000000];
int cx,cy;
long long calcx(int k,int l,int r,int lx,int rx,int ly,int ry);
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;
}
void init(int R, int C) {
cx=1;
treex[0]={-1,-1,-1};
}
void updy(int k,int l,int r,int y,long long val){
if(r<y||y<l)return;
if(l==r){
treey[k].val=val;
// cout<<k<<' '<<l<<' '<<r<<' '<<y<<' '<<val<<' '<<treey[k].val<<endl;
return;
}
if(treey[k].chl==-1){
treey[k].chl=cy;
treey[k].chr=cy+1;
treey[cy]={0,-1,-1};
treey[cy+1]={0,-1,-1};
cy+=2;
}
updy(treey[k].chl,l,(l+r)/2,y,val);
updy(treey[k].chr,(l+r)/2+1,r,y,val);
treey[k].val=gcd2(treey[treey[k].chl].val,treey[treey[k].chr].val);
// cout<<k<<' '<<l<<' '<<r<<' '<<y<<' '<<val<<' '<<treey[k].val<<endl;
}
void updx(int k,int l,int r,int x,int y,long long val){
if(k==-1||r<x||x<l)return;
if(treex[k].chy==-1){
treex[k].chy=cy;
treey[cy]={0,-1,-1};
cy++;
}
if(l!=r&&treex[k].chl==-1){
treex[k].chl=cx;
treex[k].chr=cx+1;
treex[cx]={-1,-1,-1};
treex[cx+1]={-1,-1,-1};
cx+=2;
}
if(l!=r){
updx(treex[k].chl,l,(l+r)/2,x,y,val);
updx(treex[k].chr,(l+r)/2+1,r,x,y,val);
updy(treex[k].chy,0,(1<<30)-1,y,gcd2(calcx(treex[k].chl,l,(l+r)/2,l,r,y,y),calcx(treex[k].chr,(l+r)/2+1,r,l,r,y,y)));
}
else{
updy(treex[k].chy,0,(1<<30)-1,y,val);
}
}
void update(int P, int Q, long long K) {
updx(0,0,(1<<30)-1,P,Q,K);
}
long long calcy(int k,int l,int r,int ly,int ry){
if(k==-1||r<ly||ry<l)return 0;
else if(ly<=l&&r<=ry)return treey[k].val;
else return gcd2(calcy(treey[k].chl,l,(l+r)/2,ly,ry),calcy(treey[k].chr,(l+r)/2+1,r,ly,ry));
}
long long calcx(int k,int l,int r,int lx,int rx,int ly,int ry){
if(k==-1||r<lx||rx<l)return 0;
else if(lx<=l&&r<=rx){
return calcy(treex[k].chy,0,(1<<30)-1,ly,ry);
}
else return gcd2(calcx(treex[k].chl,l,(l+r)/2,lx,rx,ly,ry),calcx(treex[k].chr,(l+r)/2+1,r,lx,rx,ly,ry));
}
long long calculate(int P, int Q, int U, int V) {
return calcx(0,0,(1<<30)-1,P,U,Q,V);
}
