#include<bits/stdc++.h>
#include "game.h"
using namespace std;
const int D=4;
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* son[D];
TreeC()
{
val=0;
for(int i=0;i<D;i++)
son[i]=NULL;
}
~TreeC()
{
for(int i=0;i<D;i++)
delete son[i];
}
void add(int l,int r,int x,long long c)
{
if(l==r)
{
val=c;
return;
}
val=0;
int d=(r-l+1)/D;
for(int i=0,j=l;i<D;i++,j+=d)
{
if(j<=x && x<j+d)
{
if(son[i]==NULL)
son[i]=new TreeC;
son[i]->add(j,j+d-1,x,c);
}
val=gcd2(val, (son[i]==NULL ? 0:son[i]->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;
long long ans=0;
int d=(r-l+1)/D;
for(int i=0,j=l;i<D;i++,j+=d)
ans=gcd2(ans, (son[i]==NULL ? 0:son[i]->read(j,j+d-1,ls,rs)));
return ans;
}
};
struct TreeR
{
TreeC *t;
TreeR* son[D];
TreeR()
{
t=new TreeC;
for(int i=0;i<D;i++)
son[i]=NULL;
}
~TreeR()
{
delete t;
for(int i=0;i<D;i++)
delete son[i];
}
void add(int l,int r,int x,int y,long long c)
{
if(l==r)
{
t->add(0,cc,y,c);
return;
}
long long tmp=0;
int d=(r-l+1)/D;
for(int i=0,j=l;i<D;i++,j+=d)
{
if(j<=x && x<j+d)
{
if(son[i]==NULL)
son[i]=new TreeR;
son[i]->add(j,j+d-1,x,y,c);
}
tmp=gcd2(tmp, (son[i]==NULL ? 0:son[i]->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);
long long ans=0;
int d=(r-l+1)/D;
for(int i=0,j=l;i<D;i++,j+=d)
ans=gcd2(ans, (son[i]==NULL ? 0:son[i]->read(j,j+d-1,ls,rs,ly,ry)));
return ans;
}
};
TreeR* root;
void init(int R,int C)
{
for(rr=1;rr<R;rr*=D);
rr--;
for(cc=1;cc<C;cc*=D);
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);
}
