#include <bits/stdc++.h>
#include "game.h"
#pragma GCC optimize ("O3")
using namespace std;
using LL = long long;
constexpr int LIM = 1e9 + 1;
int R;
int C;
LL gcd2(LL X, LL Y) {
LL tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct st {
static st * new_st(int a = 0, int b = C) {
auto ret = new st;
ret->a = a;
ret->b = b;
ret->g = 0;
return ret;
}
int a, b;
st * l = nullptr;
st * r = nullptr;
LL g = 0;
st() {}
~st() {
if (l) delete l;
if (r) delete r;
}
friend void update(st * const n, const int p, const LL k) {
if (!(n->a <= p && p < n->b)) return;
if (n->b - n->a <= 1) {
n->g = k;
return;
}
int m = (n->a+n->b) / 2;
if (p < m) {
if (!n->l) n->l = new_st(n->a, m);
update(n->l, p, k);
} else {
if (!n->r) n->r = new_st(m, n->b);
update(n->r, p, k);
}
if (!n->l) n->g = n->r->g;
else if (!n->r) n->g = n->l->g;
else n->g = gcd2(n->l->g, n->r->g);
}
friend LL query(const st * const n, const int l, const int r) {
if (!n || r <= n->a || n->b <= l) return 0LL;
if (l <= n->a && n->b <= r) return n->g;
return gcd2(query(n->l, l, r), query(n->r, l, r));
}
};
struct sst {
static sst * new_sst(int a = 0, int b = R) {
auto ret = new sst;
ret->a = a;
ret->b = b;
return ret;
}
int a, b;
sst * l = nullptr;
sst * r = nullptr;
st * son = nullptr;
sst() {}
~sst() {
if (l) delete l;
if (r) delete r;
if (son) delete son;
}
friend void sst_update(sst * const n, const int p, const int q, const LL k) {
if (!(n->a <= p && p < n->b)) return;
if (!n->son) n->son = st::new_st();
if (n->b - n->a <= 1) {
update(n->son, q, k);
return;
}
// don't update the son if b-a != 1!
// you can't just overwrite all the values in the same row, like in 1d
int m = (n->a+n->b) / 2;
if (p < m) {
if (!n->l) n->l = new_sst(n->a, m);
sst_update(n->l, p, q, k);
} else {
if (!n->r) n->r = new_sst(m, n->b);
sst_update(n->r, p, q, k);
}
// suppose n->l and n->r are either zero or up to date
// rebuild n->son properly
// update the intervals with q in n->son
rebuild(n, q);
}
friend void rebuild(sst * const n, const int q) {
int a = n->son->a;
int b = n->son->b;
st * sonn = n->son;
st * sonl = n->l ? n->l->son : nullptr;
st * sonr = n->r ? n->r->son : nullptr;
while (sonn) {
sonn->g = gcd2(sonl ? sonl->g : 0, sonr ? sonr->g : 0);
int m = (a + b) / 2;
if (q < m) {
b = m;
sonn = sonn->l;
sonl = sonl ? sonl->l : nullptr;
sonr = sonr ? sonr->l : nullptr;
} else {
a = m;
sonn = sonn->r;
sonl = sonl ? sonl->r : nullptr;
sonr = sonr ? sonr->r : nullptr;
}
}
}
friend LL sst_query(const sst * const n, const int p, const int q, const int u, const int v) {
if (!n || u <= n->a || n->b <= p) return 0LL;
if (p <= n->a && n->b <= u) return query(n->son, q, v);
return gcd2(sst_query(n->l, p, q, u, v), sst_query(n->r, p, q, u, v));
}
};
sst * root;
void cleanup() {
delete root;
}
void init(int r, int c) {
R = r+5; C = c+5; // fsr R=C=1<<30 solves fewer testcases
root = sst::new_sst();
assert(atexit(cleanup) == 0);
}
void update(int p, int q, LL k) {
sst_update(root, p, q, k);
}
long long calculate(int p, int q, int u, int v) {
return sst_query(root, p, q, u+1, v+1);
}
