#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;
int only;
long long val;
Y(int d, long long va) : left(NULL), right(NULL), only(d), val(va) {}
};
struct X
{
X *left, *right;
Y *ynode;
X() : left(NULL), right(NULL), ynode(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 (y->only >= 0)
{
if (y->only == yco)
{
y->val = v;
if (!y->left && !y->right)
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);
}
}
else
cnt += 2;
}
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);
}
}
else
cnt += 2;
}
if (cnt == 1)
{
y->only = valind;
y->val = gcd2(l, r);
return;
}
else
{
if (y->only >= 0)
{
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;
y->val = gcd2(l, r);
}
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 (m >= 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;
}
if (y->only >= 0)
{
if (py <= y->only && y->only <= qy)
{
return y->val;
}
else
return 0ll;
}
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);
}
