#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 mt(26769420);
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct node{
int pos, pri; ll val, tval;
node *l = nullptr, *r = nullptr;
node (int _pos){
pos = _pos, pri = mt(), val = tval = 0;
}
};
ll gettv(node *pt){
return (pt ? pt->tval : 0);
}
void recalc(node *pt){
pt->tval = gcd2(pt->val, gcd2(gettv(pt->l), gettv(pt->r)));
}
void split(node *pt, node *<, node *&rt, int x){
if (!pt){
lt = rt = nullptr; return;
}
if (pt->pos <= x){
split(pt->r, pt->r, rt, x); lt = pt;
}
else{
split(pt->l, lt, pt->l, x); rt = pt;
}
recalc(pt);
}
void join(node *&pt, node *lt, node *rt){
if (!lt){
pt = rt; return;
}
if (!rt){
pt = lt; return;
}
if (lt->pri > rt->pri){
pt = lt; join(lt->r, lt->r, rt);
}
else{
pt = rt; join(rt->l, lt, rt->l);
}
recalc(pt);
}
void upd(node *&pt, int x, ll v){
node *t1, *t2, *t3;
split(pt, t1, t3, x); split(t1, t1, t2, x - 1);
if (!t2) t2 = new node(x);
t2->val = t2->tval = v;
join(t1, t1, t2); join(pt, t1, t3);
}
ll qry(node *&pt, int x, int y){
node *t1, *t2, *t3;
split(pt, t1, t3, y); split(t1, t1, t2, x - 1);
ll res = gettv(t2);
join(t1, t1, t2); join(pt, t1, t3);
return res;
}
struct node2{
int s, e, m; node *t;
node2 *l = nullptr, *r = nullptr;
node2 (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1; t = nullptr;
}
void mchild(){
if (l) return;
l = new node2(s, m); r = new node2(m + 1, e);
}
void upd2(int rp, int cp, ll v){
if (s == e){
upd(t, cp, v); return;
}
mchild();
if (rp <= m) l->upd2(rp, cp, v);
else r->upd2(rp, cp, v);
upd(t, cp, gcd2(qry(l->t, cp, cp), qry(r->t, cp, cp)));
}
ll qry2(int rs, int re, int cs, int ce){
if (rs == s & re == e) return qry(t, cs, ce);
if (!l) return 0;
if (re <= m) return l->qry2(rs, re, cs, ce);
else if (rs > m) return r->qry2(rs, re, cs, ce);
else return gcd2(l->qry2(rs, m, cs, ce), r->qry2(m + 1, re, cs, ce));
}
}*root;
void init(int R, int C) {
root = new node2(0, R - 1);
}
void update(int P, int Q, ll K) {
root->upd2(P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return root->qry2(P, U, Q, V);
}
