#include "game.h"
#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;
#undef DEBUG
#ifdef DEBUG
#include "debug.h"
#else
#define debug(...) void(23)
#endif
i64 gcd(i64 a, i64 b, i64 c) {
return std::gcd(std::gcd(a, b), c);
}
std::mt19937_64 rng(23);
struct treap {
struct node {
u64 wei = rng();
int lo, hi;
int pos;
i64 val;
i64 sum;
node *lv = nullptr, *rv = nullptr;
node() {}
node(int p, i64 x) : lo(p), hi(p), pos(p), val(x), sum(x) {}
};
node *root = nullptr;
treap() {}
treap(node* v) : root(v) {}
i64 sum(node* v) { return v ? v->sum : 0; }
void pull(node*& v) {
if (!v) {
return;
}
v->sum = gcd(sum(v->lv), sum(v->rv), v->val);
v->lo = (v->lv ? v->lv->lo : v->pos);
v->hi = (v->rv ? v->rv->hi : v->pos);
}
void merge(node*& v, node* l, node* r) {
if (!l || !r) {
v = (l ? l : r);
return;
}
if (l->wei < r->wei) {
merge(r->lv, l, r->lv);
v = r;
} else {
merge(l->rv, l->rv, r);
v = l;
}
pull(v);
}
void split(node* v, node*& l, node*& r, int p) {
if (!v) {
l = nullptr;
r = nullptr;
return;
}
if (v->pos < p) {
split(v->rv, v->rv, r, p);
l = v;
} else {
split(v->lv, l, v->lv, p);
r = v;
}
pull(l);
pull(r);
}
bool find(int p) {
node* v = root;
while (v) {
if (v->pos == p) {
return true;
} else if (v->pos < p) {
v = v->rv;
} else {
v = v->lv;
}
}
return false;
}
void update(node* v, int p, i64 x) {
if (v->pos == p) {
v->val = x;
v->sum = x;
return;
} else if (v->pos < p) {
update(v->rv, p, x);
} else {
update(v->lv, p, x);
}
pull(v);
}
void update(int p, i64 x) {
update(root, p, x);
}
void insert(int p, i64 x) {
// debug("try to insert", p, x);
if (find(p)) {
// debug("found", p, x);
update(p, x);
// debug("success");
} else {
node *lv, *rv;
// debug("try to split");
split(root, lv, rv, p);
// debug("try to merge #1");
merge(lv, lv, new node(p, x));
// debug("try to merge #2");
merge(root, lv, rv);
// debug("success");
}
debug_treap();
}
i64 query(node* v, int l, int r) {
debug("query on treap: ", v->lo, v->hi, l, r);
if (v->hi < l || r < v->lo) {
return 0;
} else if (l <= v->lo && v->hi <= r) {
return v->sum;
}
i64 res = ((l <= v->pos && v->pos <= r) ? v->val : 0);
if (v->lv) res = std::gcd(res, query(v->lv, l, r));
if (v->rv) res = std::gcd(res, query(v->rv, l, r));
return res;
}
i64 query(int l, int r) {
if (!root) {
return 0;
}
debug_treap();
return query(root, l, r);
}
void debug_vertex(node* v) {
if (v->lv) debug_vertex(v->lv);
debug(v->pos, v->val, v->sum);
if (v->rv) debug_vertex(v->rv);
}
void debug_treap() {
#ifdef DEBUG
debug("treap: ");
if (root) debug_vertex(root);
debug();
#endif
}
};
struct segtree {
int lo, hi;
segtree *l = nullptr, *r = nullptr;
treap tree;
segtree() {}
segtree(int a, int b) : lo(a), hi(b) {}
void fix(int q) {
debug("try to fix", q);
i64 res = 0;
debug("try left node");
if (l) res = std::gcd(res, l->tree.query(q, q));
debug("try right node");
if (r) res = std::gcd(res, r->tree.query(q, q));
debug("add", q, res);
tree.insert(q, res);
debug("success");
}
void update(int p, int q, i64 k) {
if (lo == hi) {
debug("single treap insert: ", q, k);
tree.insert(q, k);
return;
}
int mid = (lo + hi) >> 1;
if (p <= mid) {
if (!l) {
l = new segtree(lo, mid);
}
l->update(p, q, k);
} else {
if (!r) {
r = new segtree(mid + 1, hi);
}
r->update(p, q, k);
}
fix(q);
}
i64 query(int a, int b, int c, int d) {
if (hi < a || b < lo) {
return 0;
} else if (a <= lo && hi <= b) {
return tree.query(c, d);
}
int mid = (a + b) >> 1;
i64 res = 0;
if (l) res = std::gcd(res, l->query(a, b, c, d));
if (r) res = std::gcd(res, r->query(a, b, c, d));
return res;
}
} tree;
void init(int R, int C) {
tree = segtree(0, R - 1);
}
void update(int P, int Q, i64 K) {
debug("update: ", P, Q, K);
tree.update(P, Q, K);
}
i64 calculate(int P, int Q, int U, int V) {
debug("query: ", P, Q, U, V);
return tree.query(P, U, Q, V);
}
