#include "game.h"
#include <algorithm>
#include <random>
#include <chrono>
using namespace std;
const int MAXUPD = 700000;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int vprio[MAXUPD], upd_idx, n;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct Treap {
int key;
long long val;
int prio;
long long gcd;
Treap *l;
Treap *r;
};
Treap *EMPTY_TREAP = new Treap {
0, // key
0, // val
0, // prio
0, // gcd
nullptr, // l
nullptr // r
};
struct Node {
Treap *treap;
Node *l;
Node *r;
Node() {
treap = EMPTY_TREAP;
l = r = nullptr;
}
} *root;
Treap *valTreap(int key, long long val, int prio) {
return new Treap {
key, // key
val, // val
prio, // prio
val, // gcd
EMPTY_TREAP, // l
EMPTY_TREAP // r
};
}
void update(Treap *t) {
if(t != EMPTY_TREAP) {
t->gcd = gcd2(gcd2(t->l->gcd, t->val), t->r->gcd);
}
}
pair<Treap*, Treap*> split(Treap *t, int key) {
if(t == EMPTY_TREAP) {
return {EMPTY_TREAP, EMPTY_TREAP};
}
if(t->key > key) {
auto [l, r] = split(t->l, key);
t->l = r;
update(t);
return {l, t};
}
auto [l, r] = split(t->r, key);
t->r = l;
update(t);
return {t, r};
}
Treap *merge(Treap *l, Treap *r) {
if(l == EMPTY_TREAP) {
return r;
}
if(r == EMPTY_TREAP) {
return l;
}
if(l->prio > r->prio) {
l->r = merge(l->r, r);
update(l);
return l;
}
r->l = merge(l, r->l);
update(r);
return r;
}
void updateTreap(Treap *&t, int poz, long long val) {
auto [t1, t2] = split(t, poz - 1);
auto [t3, t4] = split(t2, poz);
t = merge(t1, merge(valTreap(poz, val, vprio[upd_idx++]), t4));
}
long long queryTreap(Treap *&t, int st, int dr) {
auto [t1, t2] = split(t, st - 1);
auto [t3, t4] = split(t2, dr);
long long ret = t3->gcd;
t = merge(t1, merge(t3, t4));
return ret;
}
long long get(Node *node, int poz) {
if(node == nullptr) {
return 0;
}
return queryTreap(node->treap, poz, poz);
}
void update(Node *&node, int left, int right, int lin, int col, long long val) {
if(node == nullptr) {
node = new Node;
}
if(left == right) {
updateTreap(node->treap, col, val);
} else {
int middle = (left + right) / 2;
if(lin <= middle) {
update(node->l, left, middle, lin, col, val);
} else {
update(node->r, middle + 1, right, lin, col, val);
}
updateTreap(node->treap, col, gcd2(get(node->l, col), get(node->r, col)));
}
}
long long query(Node *node, int left, int right, int linl, int linr, int coll, int colr) {
if(node == nullptr) {
return 0;
}
if(linl <= left && right <= linr) {
return queryTreap(node->treap, coll, colr);
}
int middle = (left + right) / 2;
long long answer = 0;
if(linl <= middle) {
answer = gcd2(answer, query(node->l, left, middle, linl, linr, coll, colr));
}
if(middle < linr) {
answer = gcd2(answer, query(node->r, middle + 1, right, linl, linr, coll, colr));
}
return answer;
}
void init(int R, int C) {
n = R;
for(int i = 0; i < MAXUPD; i++) {
vprio[i] = i;
}
shuffle(vprio, vprio + MAXUPD, rng);
upd_idx = 0;
root = nullptr;
}
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 query(root, 0, n - 1, P, U, Q, V);
}
