#include "bits/extc++.h"
using namespace std;
template <typename T>
void dbgh(const T& t) {
cerr << t << endl;
}
template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
cerr << t << " | ";
dbgh(u...);
}
#ifdef DEBUG
#define dbg(...) \
cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr \
if (false) \
cerr
#endif
#define endl "\n"
#define long long long
#define sz(x) int((x).size())
struct N1 {
int lc, rc, v;
} h1[(10 << 20) / sizeof(N1)];
struct N2 {
int lc, rc;
long v;
} h2[(210 << 20) / sizeof(N2)];
int alloc1() {
static int hind = 1;
assert(hind < sizeof(h1) / sizeof(N1));
return hind++;
}
int alloc2() {
static int hind = 1;
assert(hind < sizeof(h2) / sizeof(N2));
return hind++;
}
int n, m, root;
map<int, int> rows;
extern "C" void init(int _n, int _m) {
n = _n;
m = _m;
}
long query2(int o, int l, int r, int ql, int qr) {
if (!o) {
return 0;
} else if (ql <= l && r <= qr) {
return h2[o].v;
}
auto& [lc, rc, _] = h2[o];
int mid = (l + r) / 2;
long ans = 0;
if (ql <= mid) {
ans = query2(lc, l, mid, ql, qr);
}
if (mid < qr) {
ans = gcd(ans, query2(rc, mid + 1, r, ql, qr));
}
return ans;
}
long query1(int o, int l, int r, int ql, int qr, int ql2, int qr2) {
if (!o) {
return 0;
} else if (r - l < 256) {
long ans = 0;
for (int i = max(l, ql); i <= min(r, qr); i++) {
auto it = rows.find(i);
if (it != rows.end()) {
ans = gcd(ans, query2(it->second, 0, m - 1, ql2, qr2));
}
}
return ans;
}
else if (ql <= l && r <= qr) {
return query2(h1[o].v, 0, m - 1, ql2, qr2);
}
auto& [lc, rc, _] = h1[o];
int mid = (l + r) / 2;
long ans = 0;
if (ql <= mid) {
ans = query1(lc, l, mid, ql, qr, ql2, qr2);
}
if (mid < qr) {
ans = gcd(ans, query1(rc, mid + 1, r, ql, qr, ql2, qr2));
}
return ans;
}
void update2(int& o, int l, int r, int y, long v) {
if (!o) {
o = alloc2();
}
if (l == r) {
h2[o].v = v;
return;
}
int mid = (l + r) / 2;
auto& [lc, rc, cv] = h2[o];
if (y <= mid) {
update2(lc, l, mid, y, v);
} else {
update2(rc, mid + 1, r, y, v);
}
cv = gcd(h2[lc].v, h2[rc].v);
}
void update1(int& o, int l, int r, int x, int y, long v) {
if (r - l < 256) {
return;
}
if (!o) {
o = alloc1();
}
auto& [lc, rc, cv] = h1[o];
if (l == r) {
update2(cv, 0, m - 1, y, v);
return;
}
int mid = (l + r) / 2;
if (x <= mid) {
update1(lc, l, mid, x, y, v);
} else {
update1(rc, mid + 1, r, x, y, v);
}
update2(cv, 0, m - 1, y,
gcd(query2(h1[lc].v, 0, m - 1, y, y),
query2(h1[rc].v, 0, m - 1, y, y)));
}
extern "C" void update(int x, int y, long v) {
update1(root, 0, n - 1, x, y, v);
update2(rows[x], 0, m - 1, y, v);
}
extern "C" long calculate(int x1, int y1, int x2, int y2) {
return query1(root, 0, n - 1, x1, x2, y1, y2);
}
