#include "bits/stdc++.h"
#include "game.h"
#ifdef mlocal
#include "grader.c"
#endif
using namespace std;
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef array<int, 2> ii;
// #define endl '\n'
int MXR, MXC;
struct SegmentTree {
public:
vector<ii> c;
vector<ll> tree;
int pt = 1;
void update(int i, ll val, int l, int r, int p, ii &xc, ii corresp, vector<SegmentTree> &xtree) {
if (l == r) {
if (!xc[0] and !xc[1]) tree[p] = val;
else {
ll v1 = (xc[0] and corresp[0]) ? xtree[xc[0]].tree[corresp[0]] : 0, v2 = (xc[1] and corresp[1]) ? xtree[xc[1]].tree[corresp[1]] : 0;
tree[p] = __gcd(v1, v2);
}
return;
}
int mid = (l+r)/2, s = i > mid;
if (!c[p][s]) {
tree.resize(pt+1); c.resize(pt+1);
c[p][s] = pt++;
}
if (xc[0] and (corresp[0] or p == 0)) corresp[0] = xtree[xc[0]].c[corresp[0]][s];
if (xc[1] and (corresp[1] or p == 0)) corresp[1] = xtree[xc[1]].c[corresp[1]][s];
// cout << i << " " << l << " " << r << endl;
// cout << xc[0] << " " << xc[1] << " " << corresp[0] << " " << corresp[1] << endl;
// assert(!((!!xc[0]) ^ (!!corresp[0])));
// assert(!((!!xc[1]) ^ (!!corresp[1])));
update(i, val, s ? mid+1 : l, s ? r : mid, c[p][s], xc, corresp, xtree);
tree[p] = __gcd(c[p][0] ? tree[c[p][0]] : 0, c[p][1] ? tree[c[p][1]] : 0);
}
ll query(int i, int j, int l, int r, int p) {
if (l > j or r < i) return 0;
if (l >= i and r <= j) return tree[p];
int mid = (l+r)/2;
return __gcd(c[p][0] ? query(i, j, l, mid, c[p][0]) : 0, c[p][1] ? query(i, j, mid+1, r, c[p][1]) : 0);
}
SegmentTree() {
c.resize(1); tree.resize(1);
}
};
struct SegmentTree2D {
public:
vector<ii> c;
vector<SegmentTree> tree;
int pt = 1;
void update(int i, int j, ll val, int l, int r, int p) {
if (l != r) {
int mid = (l+r)/2, s = i > mid;
if (!c[p][s]) {
tree.resize(pt+1); c.resize(pt+1);
c[p][s] = pt++;
}
update(i, j, val, s ? mid+1 : l, s ? r : mid, c[p][s]);
}
tree[p].update(j, val, 0, MXC, 0, c[p], {0, 0}, tree);
}
ll query(int xi, int xj, int yi, int yj, int l, int r, int p) {
if (l > xj or r < xi) return 0;
if (l >= xi and r <= xj) return tree[p].query(yi, yj, 0, MXC, 0);
int mid = (l+r)/2;
return __gcd(c[p][0] ? query(xi, xj, yi, yj, l, mid, c[p][0]) : 0, c[p][1] ? query(xi, xj, yi, yj, mid+1, r, c[p][1]) : 0);
}
SegmentTree2D() {
c.resize(1); tree.resize(1);
}
};
SegmentTree2D tree;
void init(int R, int C) {
// Wait, do I even need to do something here? :)
MXR = R, MXC = C;
}
void update(int P, int Q, ll K) {
tree.update(P, Q, K, 0, MXR, 0);
}
ll calculate(int P, int Q, int U, int V) {
return tree.query(P, U, Q, V, 0, MXR, 0);
// return g;
}
