#include<bits/stdc++.h>
#include "game.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;
}
int rr,cc;
struct TreeC
{
long long val;
TreeC *lson,*rson;
TreeC()
{
val=0;
lson=NULL;
rson=NULL;
}
~TreeC()
{
delete lson;
delete rson;
}
void add(int l,int r,int x,long long c)
{
if(l==r)
{
val=c;
return;
}
int mid=(l+r)/2;
if(x<=mid)
{
if(lson==NULL)
lson=new TreeC;
lson->add(l,mid,x,c);
}
else
{
if(rson==NULL)
rson=new TreeC;
rson->add(mid+1,r,x,c);
}
val=gcd2((lson==NULL ? 0:lson->val), (rson==NULL ? 0:rson->val));
return;
}
long long read(int l,int r,int ls,int rs)
{
if(rs<l || r<ls)
return 0;
if(ls<=l && r<=rs)
return val;
int mid=(l+r)/2;
return gcd2((lson==NULL ? 0:lson->read(l,mid,ls,rs)),
(rson==NULL ? 0:rson->read(mid+1,r,ls,rs)));
}
};
struct TreeR
{
TreeC *t;
TreeR *lson,*rson;
TreeR()
{
t=new TreeC;
lson=NULL;
rson=NULL;
}
~TreeR()
{
delete t;
delete lson;
delete rson;
}
void add(int l,int r,int x,int y,long long c)
{
if(l==r)
{
t->add(0,cc,y,c);
return;
}
int mid=(l+r)/2;
if(x<=mid)
{
if(lson==NULL)
lson=new TreeR;
lson->add(l,mid,x,y,c);
}
else
{
if(rson==NULL)
rson=new TreeR;
rson->add(mid+1,r,x,y,c);
}
long long tmp=gcd2((lson==NULL ? 0:lson->t->read(0,cc,y,y)),
(rson==NULL ? 0:rson->t->read(0,cc,y,y)));
t->add(0,cc,y,tmp);
return;
}
long long read(int l,int r,int ls,int rs,int ly,int ry)
{
if(rs<l || r<ls)
return 0;
if(ls<=l && r<=rs)
return t->read(0,cc,ly,ry);
int mid=(l+r)/2;
return gcd2((lson==NULL ? 0:lson->read(l,mid,ls,rs,ly,ry)),
(rson==NULL ? 0:rson->read(mid+1,r,ls,rs,ly,ry)));
}
};
TreeR* root;
void init(int R,int C)
{
for(rr=1;rr<R;rr*=2);
rr--;
for(cc=1;cc<C;cc*=2);
cc--;
root=new TreeR;
return;
}
void update(int P,int Q,long long K)
{
root->add(0,rr,P,Q,K);
return;
}
long long calculate(int P,int Q,int U,int V)
{
return root->read(0,rr,P,U,Q,V);
}
