#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int R, C, N, ch, P, Q, U, V;
int px,qx,py,qy;
int xco, yco;
long long v;
long long K;
struct Y
{
Y *left, *right ;
long long val;
int only;
Y(int d,int va): left(NULL),right(NULL),val(va),only(d){}
};
struct X
{
X *left, *right;
Y *ynode;
X():left(NULL),right(NULL){}
}*inix;
long long gcd2(long long xx, long long yy)
{
if (yy == 0)
return xx;
return gcd2(yy, xx % yy);
}
void yup(Y *y, int s,int e)
{
int m=(s + e) >>1;
if (s == e)
{
y->val = v;
return;
}
if(y->only>=0)
{
if(y->only==yco)
{
y->val=v;
return ;
}
else
{
if(y->only<=m && !y->left)
{
y->left=new Y(y->only,y->val);
}
else if(y->only>m && !y->right)
{
y->right=new Y(y->only,y->val);
}
y->only=-1;
}
}
if (m >= yco)
{
if (!y->left)
{
y->left=new Y(yco,v);
}
yup(y->left, s,m);
}
else
{
if (!y->right)
{
y->right=new Y(yco,v);
}
yup(y->right, m+1,e);
}
long long l = 0, r = 0;
if (y->left)
l = y->left->val;
if (y->right)
r = y->right->val;
y->val = gcd2(l, r);
}
void hardyup(Y *y, int s,int e, Y *ly, Y *ry)
{
int m=(s + e) >>1;
long long l = 0, r = 0;
int cnt=0,valind=-1;
if (ly)
{
l =ly->val;
if(ly->only>=0)
{
cnt++;
valind=ly->only;
if(ly->only<=m && !ly->left)
{
ly->left=new Y(ly->only,ly->val);
}
else if(ly->only >m && !ly->right)
{
ly->right=new Y(ly->only,ly->val);
}
}
}
if (ry)
{
r = ry->val;
if(ry->only>=0)
{
cnt++;
valind=ry->only;
if(ry->only<=m && !ry->left)
{
ry->left=new Y(ry->only,ry->val);
}
else if(ry->only >m && !ry->right)
{
ry->right=new Y(ry->only,ry->val);
}
}
}
y->val = gcd2(l, r);
if(cnt==1)
{
y->only=valind;
return;
}
if (s == e)
return;
if (yco <= m)
{
if (!y->left)
{
y->left = new Y(yco,v);
}
hardyup(y->left, s,m,ly?ly->left:NULL, ry?ry->left:NULL);
}
else
{
if (!y->right)
{
y->right = new Y(yco,v);
}
hardyup(y->right, m+1,e,ly?ly->right:NULL, ry?ry->right:NULL);
}
}
void xup(X *x, int s,int e)
{
int m=(s + e) >>1;
if(!x->ynode)x->ynode=new Y(yco,v);
if (s == e)
{
yup(x->ynode, 0,C-1);
return;
}
if ((s + e) / 2 >= xco)
{
if (!x->left)
{
x->left = new X();
}
xup(x->left, s,m);
}
else
{
if (!x->right)
{
x->right = new X();
}
xup(x->right, m+1,e);
}
hardyup(x->ynode, 0,C-1,x->left?x->left->ynode:NULL, x->right?x->right->ynode:NULL);
}
long long yans(Y *y, int s,int e)
{
int m=(s + e) >>1;
if ((!y)||s > qy || e < py)
return 0ll;
if (py <= s && e <= qy)
return y->val;
long long l = 0, r = 0;
if (y->left)
l = yans(y->left,s,m);
if (y->right)
r = yans(y->right, m+1,e);
return gcd2(l, r);
}
long long xans(X *x, int s,int e)
{
int m=(s + e) >>1;
if ((!x->ynode)||s > qx || e < px)
return 0ll;
if (px <= s && e <= qx)
{
return yans(x->ynode, 0,C-1);
}
long long l = 0, r = 0;
if (x->left)
l = xans(x->left, s,m);
if (x->right)
r = xans(x->right,m+1,e);
return gcd2(l, r);
}
void init(int RR, int CC)
{
R=RR;
C=CC;
inix=new X();
}
void update(int P,int Q,long long K)
{
xco=P;
yco=Q;
v=K;
xup(inix, 0,R-1);
}
long long calculate(int P,int Q,int U,int V)
{
px=P;
qx=U;
py=Q;
qy=V;
return xans(inix, 0,R-1);
}
