#include "game.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <array>
#define ll long long
#define pii pair<int, int>
#define ppi pair<pii, ll>
#define fst first
#define snd second
using namespace std;
inline ll GCD(ll X, ll Y)
{
ll tmp;
while (X != Y && Y != 0)
{
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
namespace seg
{
int r, c;
vector<pii> Cx; vector<int> Rx;
pii C[10000000]; int keep[10000001];
ll val[10000000];
int SSZ = 0;
inline int newNode()
{
C[SSZ] = {-1, -1}; keep[SSZ] = -2; SSZ++;
return SSZ - 1;
}
inline int newLine()
{
Cx.push_back({-1, -1}); Rx.push_back(-1);
Rx.back() = newNode();
return Cx.size() - 1;
}
inline void checkChildX(int u, bool b)
{
if (b && Cx[u].fst == -1)
{
int rr = newLine();
Cx[u].fst = rr;
}
if (!b && Cx[u].snd == -1)
{
int rr = newLine();
Cx[u].snd = rr;
}
}
inline void checkChildY(int u, bool b)
{
if (b && C[u].fst == -1)
{
int idx = newNode();
C[u].fst = idx;
}
if (!b && C[u].snd == -1)
{
int idx = newNode();
C[u].snd = idx;
}
}
inline int getRoot(int u)
{
if (u == -1) {return -1;}
else {return Rx[u];}
}
inline int getChild(int u, bool b)
{
if (u == -1) {return -1;}
else if (b) {return C[u].fst;}
else {return C[u].snd;}
}
inline ll getVal(int u)
{
if (u == -1) {return 0;}
return val[u];
}
void updateY(int u, int L, int R, int x, ll v)
{
if (L < R && (keep[u] != -2 && keep[u] != x))
{
int M = L + R >> 1;
if (keep[u] != -1)
{
checkChildY(u, keep[u] <= M);
if (keep[u] <= M)
{
val[C[u].fst] = val[u];
keep[C[u].fst] = keep[u];
}
else
{
val[C[u].snd] = val[u];
keep[C[u].snd] = keep[u];
}
keep[u] = -1;
}
checkChildY(u, x <= M);
if (x <= M) updateY(C[u].fst, L, M, x, v);
else updateY(C[u].snd, M + 1, R, x, v);
val[u] = GCD(getVal(C[u].fst), getVal(C[u].snd));
}
else {keep[u] = x; val[u] = v;}
}
ll queryY(int u, int L, int R, int l, int r)
{
l = max(L, l); r = min(R, r);
if (u == -1) {return 0;}
if (l <= r)
{
if (L == l && R == r) {return val[u];}
else if (keep[u] != -1)
{
if (l <= keep[u] && keep[u] <= r) return val[u];
else return 0;
}
else
{
int M = L + R >> 1;
return GCD(queryY(C[u].fst, L, M, l, r), queryY(C[u].snd, M + 1, R, l, r));
}
}
return 0;
}
void updateX(int u, int L, int R, int x, int y, ll v)
{
if (L < R)
{
int M = L + R >> 1;
checkChildX(u, x <= M);
if (x <= M) updateX(Cx[u].fst, L, M, x, y, v);
else updateX(Cx[u].snd, M + 1, R, x, y, v);
v = GCD(queryY(getRoot(Cx[u].fst), 0, r - 1, y, y), queryY(getRoot(Cx[u].snd), 0, r - 1, y, y));
}
updateY(Rx[u], 0, r - 1, y, v);
}
ll queryX(int u, int L, int R, int lx, int rx, int ly, int ry)
{
lx = max(lx, L); rx = min(rx, R);
if (u == -1) return 0;
if (lx <= rx)
{
if (L == lx && R == rx) {return queryY(Rx[u], 0, r - 1, ly, ry);}
else
{
int M = L + R >> 1;
return GCD(queryX(Cx[u].fst, L, M, lx, rx, ly, ry), queryX(Cx[u].snd, M + 1, R, lx, rx, ly, ry));
}
}
return 0;
}
}
void init(int R, int C)
{
seg :: r = R; seg :: c = C;
seg :: newLine();
}
void update(int P, int Q, ll K)
{
seg :: updateX(0, 0, seg :: c - 1, Q, P, K);
}
long long calculate(int P, int Q, int U, int V)
{
return seg :: queryX(0, 0, seg :: c - 1, Q, V, P, U);
}
