#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using T = long long;
inline T merge(const T &a, const T &b) { return gcd(a, b); }
const T default_val = 0;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
struct Treap {
struct Node {
int y, pri, mn, mx;
T val, agg;
Node *l, *r;
Node(int _y, T _v): y(_y), pri(rng()), mn(_y), mx(_y), val(_v), agg(_v), l(nullptr), r(nullptr) {}
void pull() {
agg = val;
mn = mx = y;
if(l) {
agg = ::merge(l->agg, agg);
mn = l->mn;
}
if(r) {
agg = ::merge(agg, r->agg);
mx = r->mx;
}
}
};
Node *root = nullptr;
void split(Node *cur, int y, Node *&L, Node *&R) {
if(!cur) {
L = R = nullptr;
return;
}
if(cur->y < y) {
split(cur->r, y, cur->r, R);
L = cur;
} else {
split(cur->l, y, L, cur->l);
R = cur;
}
cur->pull();
}
Node* merge(Node *L, Node *R) {
if(!L || !R) return L ? L : R;
if(L->pri < R->pri) {
L->r = merge(L->r, R);
L->pull();
return L;
} else {
R->l = merge(L, R->l);
R->pull();
return R;
}
}
void insert(int y, T v) {
Node *a, *b, *c;
split(root, y, a, b);
split(b, y + 1, b, c);
if(b) {
b->val = v;
b->pull();
} else {
b = new Node(y, v);
}
root = merge(merge(a, b), c);
}
T query(int y1, int y2) {
Node *a, *b, *c;
split(root, y1, a, b);
split(b, y2 + 1, b, c);
T ans = b ? b->agg : default_val;
root = merge(a, merge(b, c));
return ans;
}
};
struct ImplicitSegTree2D {
int lx, rx;
ImplicitSegTree2D *l = nullptr, *r = nullptr;
Treap tr;
ImplicitSegTree2D() : lx(0), rx(0) {}
ImplicitSegTree2D(int _lx, int _rx) : lx(_lx), rx(_rx) {}
void update(int x, int y, T v) {
if(lx == rx) {
tr.insert(y, v);
return;
}
int mid = (lx + rx) >> 1;
if(x <= mid) {
if(!l) l = new ImplicitSegTree2D(lx, mid);
l->update(x, y, v);
} else {
if(!r) r = new ImplicitSegTree2D(mid + 1, rx);
r->update(x, y, v);
}
T left_val = l ? l->tr.query(y, y) : default_val;
T right_val = r ? r->tr.query(y, y) : default_val;
tr.insert(y, merge(left_val, right_val));
}
T query(int x1, int y1, int x2, int y2) {
if(x2 < lx || rx < x1) return default_val;
if(x1 <= lx && rx <= x2) return tr.query(y1, y2);
T ans = default_val;
if(l) ans = merge(ans, l->query(x1, y1, x2, y2));
if(r) ans = merge(ans, r->query(x1, y1, x2, y2));
return ans;
}
};
ImplicitSegTree2D st;
void init(int R, int C) {
st = ImplicitSegTree2D(0, R - 1);
}
void update(int P, int Q, long long K) {
st.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return st.query(P, Q, U, V);
}
