#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define SZ(a) ((int)a.size())
#define pb push_back
#define ALL(v) v.begin(), v.end()
int n, m;
struct SegNode1D {
ll val = 0;
SegNode1D *lp = nullptr, *rp = nullptr;
};
struct SegmentTree1D {
SegNode1D *node;
void modify(int l, int r, SegNode1D *&p, int q, ll val) {
if (p == nullptr)
p = new SegNode1D;
if (l == r) {
p->val = val;
return;
}
int mid = l + r >> 1;
if (q <= mid)
modify(l, mid, p->lp, q, val);
else
modify(mid + 1, r, p->rp, q, val);
p->val = gcd(p->lp ? p->lp->val : 0, p->rp ? p->rp->val : 0);
}
void modify(int q, ll val) { modify(1, m, node, q, val); }
ll query(int l, int r, SegNode1D *&p, int ql, int qr) {
if (!p || ql > r || qr < l) return 0;
if (ql <= l && r <= qr)
return p->val;
int mid = l + r >> 1;
return gcd(p->lp ? query(l, mid, p->lp, ql, qr) : 0, p->rp ? query(mid + 1, r, p->rp, ql, qr) : 0);
}
ll query(int ql, int qr) { return query(1, m, node, ql, qr); }
};
struct SegNode2D {
SegmentTree1D val;
SegNode2D *lp = nullptr, *rp = nullptr;
};
struct SegmentTree2D {
SegNode2D *node;
void modify(int l, int r, SegNode2D *&p, int x, int y, ll val) {
if (p == nullptr)
p = new SegNode2D;
if (l == r) {
p->val.modify(y, val);
return;
}
int mid = l + r >> 1;
if (x <= mid)
modify(l, mid, p->lp, x, y, val);
else
modify(mid + 1, r, p->rp, x, y, val);
p->val.modify(y, gcd(p->lp ? p->lp->val.query(y, y) : 0, p->rp ? p->rp->val.query(y, y) : 0));
}
void modify(int x, int y, ll val) { modify(1, n, node, x, y, val); }
ll query(int l, int r, SegNode2D *&p, int U, int D, int L, int R) {
if (!p || U > r || D < l) return 0;
if (U <= l && r <= D)
return p->val.query(L, R);
int mid = l + r >> 1;
return gcd(p->lp ? query(l, mid, p->lp, U, D, L, R) : 0, p->rp ? query(mid + 1, r, p->rp, U, D, L, R) : 0);
}
ll query(int U, int D, int L, int R) { return query(1, n, node, U, L, D, R); }
} tree;
void init(int R, int C) {
n = R, m = C;
}
void update(int P, int Q, ll K) {
tree.modify(++P, ++Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return tree.query(++P, ++Q, ++U, ++V);
}
