#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
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 node {
node *lc, *rc;
int pos, key, tl, tr;
ll val, g;
node(int p, ll v){
lc = nullptr;
rc = nullptr;
tl = tr = pos = p;
key = rand();
val = g = v;
}
void update(){
g = val;
tl = tr = pos;
if (lc){
g = gcd(g, lc->g);
tl = lc->tl;
}
if (rc){
g = gcd(g, rc->g);
tr = rc->tr;
}
}
};
struct treap {
node* root;
treap(){
root = nullptr;
}
void split(node* t, int pos, node*& l, node*& r){
if (!t){
l = r = nullptr;
return;
}
if (t->pos < pos){
split(t->rc, pos, l, r);
t->rc = l;
l = t;
}
else {
split(t->lc, pos, l, r);
t->lc = r;
r = t;
}
t->update();
}
node* merge(node* l, node* r){
if (!l) return r;
if (!r) return l;
if (l->key < r->key){
l->rc = merge(l->rc, r);
l->update();
return l;
}
else {
r->lc = merge(l, r->lc);
r->update();
return r;
}
}
bool find(int pos){
node* t = root;
while (t){
if (t->pos == pos) return true;
if (t->pos > pos) t = t->lc;
else t = t->rc;
}
return false;
}
void update(node* t, int pos, ll val){
if (t->pos == pos){
t->val = val;
t->update();
return;
}
if (t->pos > pos) update(t->lc, pos, val);
else update(t->rc, pos, val);
}
void insert(int pos, ll val){
if (find(pos)) update(root, pos, val);
else {
node *l, *r;
split(root, pos, l, r);
root = merge(l, merge(new node(pos, val), r));
}
}
ll query(node* t, int lb, int rb){
if (t->tr < lb || rb < t->tl) return 0;
if (lb <= t->tl && t->tr <= rb) return t->g;
ll ans = 0;
if (lb <= t->pos && t->pos <= rb) ans = t->val;
if (t->lc) ans = gcd2(ans, query(t->lc, lb, rb));
if (t->rc) ans = gcd2(ans, query(t->rc, lb, rb));
return ans;
}
ll query(int lb, int rb){
if (root) return query(root, lb, rb);
return 0;
}
};
struct st {
st *lc, *rc;
treap *t;
int tl, tr;
st(int lb, int rb){
lc = rc = nullptr;
tl = lb;
tr = rb;
t = new treap();
}
void fix(int pos){
ll val = 0;
if (lc) val = gcd(val, lc->t->query(pos, pos));
if (rc) val = gcd(val, rc->t->query(pos, pos));
t->insert(pos, val);
}
void update(int x, int y, ll val){
if (x < tl || tr < x) return;
if (tl == tr){
t->insert(y, val);
return;
}
int tm = (tl+tr)/2;
if (x <= tm){
if (!lc) lc = new st(tl, tm);
lc->update(x, y, val);
}
else {
if (!rc) rc = new st(tm+1, tr);
rc->update(x, y, val);
}
fix(y);
}
ll query(int xl, int xr, int yl, int yr){
if (xr < tl || tr < xl) return 0;
if (xl <= tl && tr <= xr) return t->query(yl, yr);
ll ans = 0;
if (lc) ans = gcd2(ans, lc->query(xl, xr, yl, yr));
if (rc) ans = gcd2(ans, rc->query(xl, xr, yl, yr));
return ans;
}
};
st* grid;
void init(int R, int C) {
grid = new st(0, R+5);
}
void update(int P, int Q, ll K){
grid->update(P, Q, K);
}
ll calculate(int P, int Q, int U, int V){
return grid->query(P, U, Q, V);
}
