#include <bits/stdc++.h>
#include "game.h"
using namespace std;
const int mod = 1e9 + 9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct treapNode {
treapNode* l;
treapNode* r;
int key, prior;
int64_t val, gcd;
};
using ptr = treapNode*;
using pt = pair<ptr, ptr>;
ptr NIL = new treapNode{nullptr, nullptr, 0, -1, 0, 0};
int64_t gcd2(int64_t X, int64_t Y) {
int64_t tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void updateNode(ptr &x) {
if (x != NIL) {
x->gcd = gcd2(gcd2(x->l->gcd, x->val), x->r->gcd);
}
}
pt split(ptr &x, int k) {
if (x == NIL) {
return {NIL, NIL};
}
if (k < x->key) {
pt p = split(x->l, k);
x->l = p.second;
updateNode(x);
return {p.first, x};
}
pt p = split(x->r, k);
x->r = p.first;
updateNode(x);
return {x, p.second};
}
ptr join(ptr x, ptr y) {
if (x == NIL) {
return y;
}
if (y == NIL) {
return x;
}
if (y->prior < x->prior) {
x->r = join(x->r, y);
updateNode(x);
return x;
}
y->l = join(x, y->l);
updateNode(y);
return y;
}
bool check(ptr &x, int k, int64_t v) {
if (x == NIL) {
return false;
}
if (x->key == k) {
x->val = v;
updateNode(x);
return true;
}
if (k < x->key) {
bool ret = check(x->l, k, v);
updateNode(x);
return ret;
} else {
bool ret = check(x->r, k, v);
updateNode(x);
return ret;
}
}
ptr ins(ptr &x, int k, int64_t v) {
if (check(x, k, v)) {
return x;
}
pt p = split(x, k);
ptr newNode = new treapNode{NIL, NIL, k, rng() % mod, v, v};
return join(join(p.first, newNode), p.second);
}
int64_t queryY(ptr &x, int st, int dr) {
pt p1 = split(x, st - 1);
pt p2 = split(p1.second, dr);
int64_t ans = p2.first->gcd;
p1.second = join(p2.first, p2.second);
x = join(p1.first, p1.second);
return ans;
}
struct sgtNode {
ptr root;
sgtNode* l;
sgtNode* r;
sgtNode() : root(NIL), l(nullptr), r(nullptr) {}
} *root;
void update(sgtNode* &x, int lx, int rx, int X, int Y, int64_t v) {
if (!x) {
x = new sgtNode();
}
x->root = ins(x->root, Y, v);
if (lx == rx) {
return;
}
int mid = (lx + rx) / 2;
if (X <= mid) {
update(x->l, lx, mid, X, Y, v);
} else {
update(x->r, mid + 1, rx, X, Y, v);
}
int64_t gcd = 0;
if (x->l) {
gcd = queryY(x->l->root, Y, Y);
}
if (x->r) {
gcd = gcd2(gcd, queryY(x->r->root, Y, Y));
}
ins(x->root, Y, gcd);
}
int64_t queryX(sgtNode* &x, int lx, int rx, int x1, int x2, int y1, int y2) {
if (!x) {
return 0;
}
if (x1 <= lx && rx <= x2) {
return queryY(x->root, y1, y2);
}
int mid = (lx + rx) / 2;
int64_t ans = 0;
if (x1 <= mid) {
ans = gcd2(ans, queryX(x->l, lx, mid, x1, x2, y1, y2));
}
if (mid < x2) {
ans = gcd2(ans, queryX(x->r, mid + 1, rx, x1, x2, y1, y2));
}
return ans;
}
int N;
void init(int R, int C) {
N = R;
}
void update(int P, int Q, long long K) {
update(root, 0, N - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(root, 0, N - 1, P, U, Q, V);
}
