#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
struct segtree {
int l, r;
ll d = 0;
segtree *left = nullptr, *right = nullptr;
void pull() {
d = gcd(left ? left->d : 0, right ? right->d : 0);
}
void update(int i, ll k) {
if (l + 1 == r) {
d = k;
} else {
int mid = (l + r) / 2;
if (i < mid) {
if (!left) {
left = new segtree({l, mid});
}
left->update(i, k);
} else {
if (!right) {
right = new segtree({mid, r});
}
right->update(i, k);
}
pull();
}
}
ll query(int lx, int rx) {
if (lx >= r || rx <= l) {
return 0;
} else if (lx <= l && r <= rx) {
return d;
} else {
ll ans = 0;
if (left) {
ans = gcd(ans, left->query(lx, rx));
}
if (right) {
ans = gcd(ans, right->query(lx, rx));
}
return ans;
}
}
ll query(int i) {
if (l + 1 == r) {
return d;
} else {
int mid = (l + r) / 2;
ll ans = 0;
if (mid > i && left) {
ans = gcd(ans, left->query(i));
}
if (mid <= i && right) {
ans = gcd(ans, right->query(i));
}
return ans;
}
}
};
int R, C;
struct SegmentTree {
int l, r;
segtree *st = nullptr;
int left = 0, right = 0;
};
constexpr int N = 22001 * 31 + 1;
SegmentTree t[N];
int node_counter = 1;
int create(int l, int r) {
t[node_counter] = SegmentTree({l, r});
return node_counter++;
}
void build_st(int x) {
if (!t[x].st) {
t[x].st = new segtree({0, C});
}
}
ll simple_query(int x, int y) {
if (!t[x].st) {
return 0;
} else {
return t[x].st->query(y);
}
}
void update(int v, int x, int y, ll k) {
build_st(v);
if (t[v].l + 1 == t[v].r) {
t[v].st->update(y, k);
} else {
int mid = (t[v].l + t[v].r) / 2;
if (x < mid) {
if (!t[v].left) {
t[v].left = create(t[v].l, mid);
}
update(t[v].left, x, y, k);
} else {
if (!t[v].right) {
t[v].right = create(mid, t[v].r);
}
update(t[v].right, x, y, k);
}
t[v].st->update(y, gcd(simple_query(t[v].left, y), simple_query(t[v].right, y)));
}
}
ll query(int v, int lx, int rx, int ly, int ry) {
if (t[v].l >= rx || lx >= t[v].r || !t[v].st) {
return 0;
} else if (lx <= t[v].l && t[v].r <= rx) {
return t[v].st->query(ly, ry);
} else {
ll ans = 0;
if (t[v].left) {
ans = gcd(ans, query(t[v].left, lx, rx, ly, ry));
}
if (t[v].right) {
ans = gcd(ans, query(t[v].right, lx, rx, ly, ry));
}
return ans;
}
}
void init(int R, int C) {
::R = R, ::C = C;
create(0, R);
}
void update(int P, int Q, ll K) {
update(1, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return query(1, P, U + 1, Q, V + 1);
}
