#include <random>
#include "game.h"
// global
typedef long long int ll;
static ll gcd2(ll u, ll v) {
while (v) {
ll tmp = u % v;
u = v;
v = tmp;
}
return u;
}
static std::mt19937 RAND(314159);
// Treap (1d bst)
class Treap {
public:
uint32_t rr;
Treap *left, *right;
int idx;
ll val, gg;
Treap(int i1, ll i2) : idx(i1), val(i2), gg(i2) {
left = right = nullptr;
rr = RAND();
}
~Treap() {
delete left;
delete right;
}
void recalc() {
this->gg = gcd2(gcd2((left ? left->gg : 0LL), (right ? right->gg : 0LL)), this->val);
}
};
static void treap_split(Treap* root, int p, Treap *&left, Treap *&right) {
if (!root) {
left = right = nullptr;
return;
}
else if (p > root->idx) {
treap_split(root->right, p, root->right, right);
left = root;
}
else {
treap_split(root->left, p, left, root->left);
right = root;
}
root->recalc();
}
static Treap* treap_merge(Treap *left, Treap *right) {
if (!left) return right;
else if (!right) return left;
else if (left->rr > right->rr) {
left->right = treap_merge(left->right, right);
left->recalc();
return left;
}
else {
right->left = treap_merge(left, right->left);
right->recalc();
return right;
}
}
static void treap_insert(Treap *&root, int p, ll k) {
Treap *p1, *p2, *p3;
treap_split(root, p, p1, p2);
treap_split(p2, p + 1, p2, p3);
if (p2) {
p2->val = p2->gg = k;
} else {
p2 = new Treap(p, k);
}
root = treap_merge(treap_merge(p1, p2), p3);
}
static ll treap_query(Treap *&root, int ln, int rn) {
Treap *p1, *p2, *p3;
if (!root) return 0LL;
else if (ln > rn) return 0LL;
else if (ln == rn) {
for (p1 = root; p1; ) {
if (p1->idx < ln) p1 = p1->right;
else if (p1->idx > ln) p1 = p1->left;
else return p1->val;
}
return 0LL;
}
treap_split(root, ln, p1, p2);
treap_split(p2, rn + 1, p2, p3);
const ll ans = (p2 ? p2->gg : 0LL);
root = treap_merge(treap_merge(p1, p2), p3);
return ans;
}
// Segment Tree (2d seg)
class Segtree {
public:
int ldx, rdx;
Segtree *left, *right;
Treap* bst;
Segtree(int l1, int r1) : ldx(l1), rdx(r1) {
left = right = nullptr;
bst = nullptr;
}
~Segtree() {
delete left;
delete right;
delete bst;
}
};
static void segtree_insert(Segtree *root, int xx, int yy, ll p) {
const int mdx = (root->ldx + root->rdx) / 2;
if (root->ldx == root->rdx) {
treap_insert(root->bst, yy, p);
return;
} else if (xx <= mdx) {
if (!root->left) root->left = new Segtree(root->ldx, mdx);
segtree_insert(root->left, xx, yy, p);
} else {
if (!root->right) root->right = new Segtree(mdx + 1, root->rdx);
segtree_insert(root->right, xx, yy, p);
}
const ll ans = gcd2((root->left ? treap_query(root->left->bst, yy, yy) : 0LL), (root->right ? treap_query(root->right->bst, yy, yy) : 0LL));
treap_insert(root->bst, yy, ans);
}
static ll segtree_query(Segtree *root, int x1, int x2, int y1, int y2) {
if (x1 < root->ldx) x1 = root->ldx;
if (x2 > root->rdx) x2 = root->rdx;
const int mdx = (root->ldx + root->rdx) / 2;
if (x1 > x2) return 0LL;
else if (root->ldx == x1 && x2 == root->rdx) return treap_query(root->bst, y1, y2);
else if (x2 <= mdx) return (root->left ? segtree_query(root->left, x1, x2, y1, y2) : 0LL);
else if (x1 > mdx) return (root->right ? segtree_query(root->right, x1, x2, y1, y2) : 0LL);
return gcd2((root->left ? segtree_query(root->left, x1, mdx, y1, y2) : 0LL), (root->right ? segtree_query(root->right, mdx + 1, x2, y1, y2) : 0LL));
}
// Starts from here
static Segtree *Idx;
void init(int R, int C) {
Idx = new Segtree(0, R - 1);
}
void update(int P, int Q, ll K) {
return segtree_insert(Idx, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return segtree_query(Idx, P, U, Q, V);
}
