#include "game.h"
#include <bits/stdc++.h>
typedef long long i64;
i64 gcd(i64 X, i64 Y) {
i64 tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Node {
int x, lx, rx;
i64 v, s;
int sz;
int ls, rs;
} t[22000 * 35];
const int null = 0;
int ndsz;
int new_node(int x, i64 v) {
int i = ++ ndsz;
t[i].x = t[i].lx = t[i].rx = x;
t[i].v = t[i].s = v;
t[i].sz = 1;
t[i].ls = t[i].rs = null;
return i;
}
void pushup(int x) {
t[x].sz = t[t[x].ls].sz + 1 + t[t[x].rs].sz;
t[x].s = gcd(t[t[x].ls].s, gcd(t[x].v, t[t[x].rs].s));
t[x].lx = t[x].ls ? t[t[x].ls].lx : t[x].x;
t[x].rx = t[x].rs ? t[t[x].rs].rx : t[x].x;
}
void split(int x, i64 v, int &a, int &b) {
if (!x) return void(a = b = null);
if (t[x].x <= v) a = x, split(t[x].rs, v, t[a].rs, b), pushup(a);
else b = x, split(t[x].ls, v, a, t[b].ls), pushup(b);
}
std::mt19937 rng;
int rand(int l, int r) { return rng() % (r - l + 1) + l; }
int merge(int a, int b) {
if (!a || !b) return a | b;
if (rand(1, t[a].sz + t[b].sz) <= t[a].sz) return t[a].rs = merge(t[a].rs, b), pushup(a), a;
else return t[b].ls = merge(a, t[b].ls), pushup(b), b;
}
void change(int &i, int p, i64 v) {
int a, b, c;
split(i, p, b, c);
split(b, p - 1, a, b);
if (!b) b = new_node(p, v);
else t[b].v = t[b].s = v;
i = merge(merge(a, b), c);
}
i64 query(int i, int l, int r) {
if (i == null) return 0;
if (l <= t[i].lx && t[i].rx <= r) return t[i].s;
if (r < t[i].lx || t[i].rx < l) return 0;
i64 ans = 0;
if (l <= t[i].x && t[i].x <= r) ans = gcd(ans, t[i].v);
if (l < t[i].x && t[i].ls) ans = gcd(ans, query(t[i].ls, l, r));
if (r > t[i].x && t[i].rs) ans = gcd(ans, query(t[i].rs, l, r));
return ans;
}
struct SegNode {
int nd;
SegNode *ls, *rs;
};
void change(int x, int y, i64 v, SegNode *&i, int a, int b) {
if (!i) i = new SegNode{0, nullptr, nullptr};
if (a + 1 == b) return change(i->nd, y, v);
int m = (a + b) >> 1;
if (x < m) change(x, y, v, i->ls, a, m);
else change(x, y, v, i->rs, m, b);
change(i->nd, y, gcd(i->ls ? query(i->ls->nd, y, y) : 0, i->rs ? query(i->rs->nd, y, y) : 0));
}
i64 query(int l, int r, int L, int R, SegNode *i, int a, int b) {
if (!i) return 0;
if (l <= a && b <= r) return query(i->nd, L, R);
if (r <= a || b <= l) return 0;
int m = (a + b) >> 1;
return gcd(query(l, r, L, R, i->ls, a, m), query(l, r, L, R, i->rs, m, b));
}
int R, C;
SegNode *rt;
void init(int _R, int _C) {
R = _R; C = _C;
rt = nullptr;
}
void update(int P, int Q, i64 K) {
change(P, Q, K, rt, 0, R);
}
i64 calculate(int P, int Q, int U, int V) {
return query(P, U + 1, Q, V, rt, 0, R);
}
#ifdef DEBUG
#include "grader.c"
#endif
