#include "game.h"
#include <stdio.h>
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;
}
struct A
{
int nxl,nxr,nxt;
long long con;
}Node[20250005];
long long N,M,now=1;
void New(int l,int r,int here,int t)
{
Node[here].nxt=t;
Node[here].nxl=-1;
Node[here].nxr=-1;
Node[here].con=0;
}
void init(int R, int C)
{
N=R;
M=C;
New(0,N-1,0,-1);
}
void Merge(int here,int l,int r,int what,int lll,int rrr)
{
int ll,rr;
if(what==lll&&what==rrr)
{
Node[here].con=0;
if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
return;
}
if(what<=(lll+rrr)/2)
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(lll,(lll+rrr)/2,Node[here].nxl,-2);
}
if(l!=-1) ll=Node[l].nxl;
if(r!=-1) rr=Node[r].nxl;
Merge(Node[here].nxl,ll,rr,what,lll,(lll+rrr)/2);
Node[here].con=0;
if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
}
else
{
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((lll+rrr)/2+1,rrr,Node[here].nxr,-2);
}
if(l!=-1) ll=Node[l].nxr;
if(r!=-1) rr=Node[r].nxr;
Merge(Node[here].nxr,ll,rr,what,(lll+rrr)/2+1,rrr);
Node[here].con=0;
if(l!=-1) Node[here].con=gcd2(Node[here].con,Node[l].con);
if(r!=-1) Node[here].con=gcd2(Node[here].con,Node[r].con);
}
//printf("%d %d %d\n",lll,rrr,Node[here].con);
}
void cha(int l,int r,int x,int y,long long con,int here)
{
if(Node[here].nxt==-2)
{
if(y==l&&y==r)
{
Node[here].con=con;
return;
}
if(y<=(l+r)/2)
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(l,(l+r)/2,Node[here].nxl,-2);
}
cha(l,(l+r)/2,x,y,con,Node[here].nxl);
Node[here].con=Node[Node[here].nxl].con;
if(Node[here].nxr!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxr].con);
}
else
{
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((l+r)/2+1,r,Node[here].nxr,-2);
}
cha((l+r)/2+1,r,x,y,con,Node[here].nxr);
Node[here].con=Node[Node[here].nxr].con;
if(Node[here].nxl!=-1) Node[here].con=gcd2(Node[here].con,Node[Node[here].nxl].con);
}
//if(y==76) printf("%lld %lld %lld %lld\n",y,l,r,Node[here].con);
}
else
{
if(x==l&&x==r)
{
if(Node[here].nxt==-1)
{
Node[here].nxt=now++;
New(0,M-1,Node[here].nxt,-2);
}
cha(0,M-1,x,y,con,Node[here].nxt);
return;
}
if(x<=(l+r)/2)
{
if(Node[here].nxl==-1)
{
Node[here].nxl=now++;
New(l,(l+r)/2,Node[here].nxl,-1);
}
cha(l,(l+r)/2,x,y,con,Node[here].nxl);
}
else
{
if(Node[here].nxr==-1)
{
Node[here].nxr=now++;
New((l+r)/2+1,r,Node[here].nxr,-1);
}
cha((l+r)/2+1,r,x,y,con,Node[here].nxr);
}
if(Node[here].nxt==-1)
{
Node[here].nxt=now++;
New(0,M-1,Node[here].nxt,-2);
}
//printf("aa %d %d\n",l,r);
Merge(Node[here].nxt,Node[Node[here].nxl].nxt,Node[Node[here].nxr].nxt,y,0,M-1);
}
}
long long Find(int l,int r,int x1,int y1,int x2,int y2,int here)
{
//printf("%lld %lld %lld %lld %lld\n",x1,y1,x2,y2,here);
if(here==-1) return 0;
if(Node[here].nxt==-2)
{
if(l==x2&&r==y2)
{
//printf("%lld %lld %lld\n",x2,y2,Node[here].con);
return Node[here].con;
}
if(y2<=(l+r)/2) return Find(l,(l+r)/2,x1,y1,x2,y2,Node[here].nxl);
if(x2>(l+r)/2) return Find((l+r)/2+1,r,x1,y1,x2,y2,Node[here].nxr);
return gcd2(Find(l,(l+r)/2,x1,y1,x2,(l+r)/2,Node[here].nxl),Find((l+r)/2+1,r,x1,y1,(l+r)/2+1,y2,Node[here].nxr));
}
else
{
if(l==x1&&r==y1) return Find(0,M-1,x1,y1,x2,y2,Node[here].nxt);
if(y1<=(l+r)/2) return Find(l,(l+r)/2,x1,y1,x2,y2,Node[here].nxl);
if(x1>(l+r)/2) return Find((l+r)/2+1,r,x1,y1,x2,y2,Node[here].nxr);
return gcd2(Find(l,(l+r)/2,x1,(l+r)/2,x2,y2,Node[here].nxl),Find((l+r)/2+1,r,(l+r)/2+1,y1,x2,y2,Node[here].nxr));
}
}
void update(int P, int Q, long long K)
{
cha(0,N-1,P,Q,K,0);
}
long long calculate(int P, int Q, int U, int V)
{
long long ans=0,i;
//printf("aaa\n");
ans=Find(0,N-1,P,U,Q,V,0);
/*for(i=P;i<=U;i++)
{
ans=gcd2(ans,Find(i,i,Q,V,0));
//if(P==60) printf("%lld %lld\n",i,Find(i,i,Q,V,0));
}*/
//printf("cc %lld\n",ans);
return ans;
}
