#include <bits/stdc++.h>
#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> struct treap{
struct node{
T pos, val, G, pri;
node *l, *r;
node(int pos_, T val_){
pos = pos_; val = val_; pri = rng();
l = r = NULL;
}
void cal(){ G = __gcd(val, __gcd((l ? l->G : 0), (r ? r->G : 0))); }
}*root;
treap(){ root = new node(0, 0); }
pair<node*, node*> split(node* t, int v){ // <= v on left
if (!t) return {t, t};
if (t->pos <= v){
auto p = split(t->r, v);
t->r = p.first; t->cal();
return {t, p.second};
}
else{
auto p = split(t->l, v);
t->l = p.second; t->cal();
return {p.first, t};
}
}
node* merge(node* l, node* r){ // l is before r
if (!l or !r) return l ? l : r;
if (l->pri < r->pri){
l->r = merge(l->r, r); l->cal();
return l;
}
else{
r->l = merge(l, r->l); r->cal();
return r;
}
}
void upd(int ind, T k){
auto [L, Rpart] = split(root, ind - 1);
auto [M, R] = split(Rpart, ind);
root = merge(merge(L, new node(ind, k)), R);
}
T qry(int l, int r){
auto [L, Rpart] = split(root, l - 1);
auto [M, R] = split(Rpart, r);
T res = M ? M->G : 0;
root = merge(merge(L, M), R);
return res;
}
};
template<class T> struct seg2d{
vector<treap<T>> seg{treap<T>(), treap<T>()}; vector<int> lc{0, 0}, rc{0, 0};
int ext(int i){
if (i) return i;
seg.push_back(treap<T>()); lc.push_back(0); rc.push_back(0);
return seg.size() - 1;
}
void upd(int ptX, int ptY, T v, int l = 0, int r = 1e9, int i = 1){
if (l == r){ seg[i].upd(ptY, v); return; }
int mid = (l + r) / 2;
if (ptX <= mid) upd(ptX, ptY, v, l, mid, lc[i] = ext(lc[i]));
else upd(ptX, ptY, v, mid + 1, r, rc[i] = ext(rc[i]));
seg[i].upd(ptY, __gcd(seg[lc[i]].qry(ptY, ptY), seg[rc[i]].qry(ptY, ptY)));
}
T qry(int qx1, int qy1, int qx2, int qy2, int l = 0, int r = 1e9, int i = 1){
if (!i or r < qx1 or l > qx2) return 0;
if (l >= qx1 and r <= qx2) return seg[i].qry(qy1, qy2);
int mid = (l + r) / 2;
return __gcd(qry(qx1, qy1, qx2, qy2, l, mid, lc[i]), qry(qx1, qy1, qx2, qy2, mid + 1, r, rc[i]));
}
};
seg2d<long long> ST;
void init(int r, int c){};
void update(int p, int q, long long k){ ST.upd(p, q, k); }
long long calculate(int p, int q, int u, int v){ return ST.qry(p, q, u, v); }
