#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "game.h"
const int INF = 1e9;
const int KK = 300;
ll gcd(ll x, ll y) {
ll tmp;
while (x != y && y != 0) {
tmp = x;
x = y;
y = tmp % y;
}
return x;
}
struct block {
int xl, xr, n;
vector<pair<pii, ll>> cut;
vector<int> y;
vector<ll> t;
int id(int v) {
return (int)(lower_bound(all(y), v) - y.begin());
}
block(vector<pair<pii, ll>> _cut) : cut(_cut) {
assert(cut.size());
xl = INF, xr = -INF;
for (auto e : cut) {
xl = min(xl, e.x.x);
xr = max(xr, e.x.x);
y.push_back(e.x.y);
}
n = (int)y.size();
sort(all(y));
t.assign(2 * n, 0);
for (auto e : cut) {
int v = n + id(e.x.y);
t[v] = gcd(t[v], e.y);
}
for (int i = n - 1; i > 0; --i) {
t[i] = gcd(t[i + i], t[i + i + 1]);
}
}
ll query(int l, int r) {
l = id(l), r = id(r + 1) - 1;
// cout << "query " << l << " " << r << endl;
// for (int i = 0; i < n; ++i) {
// cout << t[i + n] << " ";
// }
// cout << endl;
ll res = 0;
for (l += n, r += n; l <= r; l /= 2, r /= 2) {
if (l % 2 == 1) {
res = gcd(res, t[l++]);
}
if (r % 2 == 0) {
res = gcd(res, t[r--]);
}
}
return res;
}
};
map<pii, ll> updates;
vector<block> blocks;
void init(int r, int c) {
(void)r; (void)c;
}
void update(int p, int q, ll k) {
auto cur = mp(p, q);
updates[cur] = k;
blocks.clear();
vector<pair<pii, ll>> buf;
for (auto e : updates) {
while (buf.size() && buf.back().x == e.x) {
buf.pop_back();
}
}
for (auto e : updates) {
buf.push_back(e);
if ((int)buf.size() == KK) {
blocks.emplace_back(buf);
buf.clear();
}
}
if (buf.size()) {
blocks.emplace_back(buf);
buf.clear();
}
}
ll calculate(int p, int q, int u, int v) {
ll ans = 0;
for (auto e : blocks) {
if (e.xr < p || e.xl > u) {
continue;
}
if (p <= e.xl && e.xr <= u) {
ans = gcd(ans, e.query(q, v));
continue;
}
for (auto i : e.cut) {
if (p <= i.x.x && i.x.x <= u && q <= i.x.y && i.x.y <= v) {
ans = gcd(ans, i.y);
}
}
}
return ans;
}
#ifdef LC
#include "grader.c"
#endif
