#include <algorithm>
#include <random>
#include "game.h"
using namespace std;
typedef long long ll;
ll gcd(ll x, ll y) {
while (x > 0) {
ll r = y % x;
y = x;
x = r;
}
return y;
}
mt19937 gen;
struct n1d {
n1d *l, *r;
int x, y;
ll g;
ll vl;
n1d(int x_, ll vl_) : x(x_), vl(vl_) {
l = nullptr;
r = nullptr;
y = uniform_int_distribution<int>(numeric_limits<int>::min(), numeric_limits<int>::max())(gen);
g = vl;
}
void upd() {
g = vl;
if (l) g = gcd(l->g, g);
if (r) g = gcd(r->g, g);
}
};
n1d* merge(n1d* a, n1d* b) {
if (!a) return b;
if (!b) return a;
if (a->y > b->y) {
a->r = merge(a->r, b);
a->upd();
return a;
}
else {
b->l = merge(a, b->l);
b->upd();
return b;
}
}
pair<n1d*, n1d*> split(n1d* a, int x) { // <= x | > x
if (!a) return { nullptr, nullptr };
if (a->x <= x) {
pair<n1d*, n1d*> p = split(a->r, x);
a->r = p.first;
a->upd();
return { a, p.second };
}
else {
pair<n1d*, n1d*> p = split(a->l, x);
a->l = p.second;
a->upd();
return {p.first, a};
}
}
void insert(n1d* &root, int x, ll vl) {
pair<n1d*, n1d*> p1 = split(root, x - 1);
pair<n1d*, n1d*> p2 = split(p1.second, x);
root = merge(p1.first, merge(new n1d(x, vl), p2.second));
}
ll ask(n1d*& root, int l, int r) {
pair<n1d*, n1d*> p1 = split(root, l - 1);
pair<n1d*, n1d*> p2 = split(p1.second, r);
ll res = 0;
if (p2.first) {
res = p2.first->g;
}
root = merge(p1.first, merge(p2.first, p2.second));
return res;
}
struct n2d {
n2d* l, * r;
int lx, rx;
n1d* tree;
n2d(int lx_, int rx_) : lx(lx_), rx(rx_) {
l = nullptr;
r = nullptr;
tree = nullptr;
}
};
void upd(n2d* v, int p, int q, ll k) {
insert(v->tree, q, k);
if (v->rx - v->lx == 1) return;
int m = (v->lx + v->rx) / 2;
if (p < m) {
if (!v->l) {
v->l = new n2d(v->lx, m);
}
upd(v->l, p, q, k);
}
else {
if (!v->r) {
v->r = new n2d(m, v->rx);
}
upd(v->r, p, q, k);
}
}
ll get(n2d* v, int lx, int rx, int ly, int ry) {
if (!v) return 0ll;
if (lx >= v->rx || v->lx >= rx) return 0ll;
if (v->lx >= lx && v->rx <= rx) return ask(v->tree, ly, ry);
return gcd(get(v->l, lx, rx, ly, ry), get(v->r, lx, rx, ly, ry));
}
n2d* root;
void init(int R, int C) {
root = new n2d(0, R);
}
void update(int P, int Q, long long K) {
upd(root, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return get(root, P, U + 1, Q, V);
}
