#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
typedef pair<int, int> ii;
typedef long long ll;
const int inf = 1e9+10;
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{
struct node{
ii pos;
int prior;
ll val, res;
node *lef, *rig;
node(ii p = mp(0, 0), ll v = 0){
pos = p;
prior = rand();
val = v;
res = v;
lef = NULL;
rig = NULL;
}
};
// try using my own null
typedef node *pnode;
pnode root;
treap(){
root = NULL;
}
void upd(pnode t){
if (t == NULL)
return;
t->res = t->val;
if (t->lef != NULL)
t->res = gcd2(t->res, t->lef->res);
if (t->rig != NULL)
t->res = gcd2(t->res, t->rig->res);
}
void split(pnode t, pnode &l, pnode &r, ii k){
if (t == NULL)
return void(l = r = NULL);
if (t->pos <= k)
split(t->rig, t->rig, r, k), l = t;
else
split(t->lef, l, t->lef, k), r = t;
upd(t);
}
void join(pnode &t, pnode l, pnode r){
if (l == NULL)
return void(t = r);
if (r == NULL)
return void(t = l);
if (l->prior > r->prior)
join(l->rig, l->rig, r), t = l;
else
join(r->lef, l, r->lef), t = r;
upd(t);
}
void add(ii p, ll v){
pnode l = NULL, mid = NULL, r = NULL;
split(root, l, r, p);
split(l, l, mid, mp(p.fi, p.se-1));
mid = new node(p, v);
join(l, l, mid);
join(root, l, r);
}
ll ask(int a, int b){
pnode l = NULL, mid = NULL, r = NULL;
split(root, l, r, mp(b, inf));
split(l, l, mid, mp(a-1, inf));
ll ans = 0;
if (mid != NULL)
ans = mid->res;
join(l, l, mid);
join(root, l, r);
return ans;
}
};
struct seg_tree{
struct node{
treap tree;
node *lef, *rig;
node(node *l = NULL, node *r = NULL){
tree = treap();
lef = l;
rig = r;
}
};
typedef node *pnode;
pnode root, null;
int mx;
seg_tree(int m = 0){
null = new node();
null->lef = null->rig = null;
root = null;
mx = m;
}
pnode update(pnode t, int l, int r, int i, int j, ll v){
if (t == null)
t = new node(null, null);
t->tree.add(mp(j, i), v);
if (l == r)
return t;
int mid = (l+r)/2;
if (i <= mid)
t->lef = update(t->lef, l, mid, i, j, v);
else
t->rig = update(t->rig, mid+1, r, i, j, v);
return t;
}
void add(int r, int c, ll v){
root = update(root, 0, mx-1, r, c, v);
}
ll query(pnode t, int l, int r, int i, int j, int a, int b){
if (r < i || j < l)
return 0;
if (i <= l && r <= j)
return t->tree.ask(a, b);
int mid = (l+r)/2;
return gcd2(query(t->lef, l, mid, i, j, a, b), query(t->rig, mid+1, r, i, j, a, b));
}
ll ask(int ar, int br, int ac, int bc){
return query(root, 0, mx-1, ar, br, ac, bc);
}
};
seg_tree data;
void init(int R, int C) {
data = seg_tree(R);
}
void update(int P, int Q, long long K) {
data.add(P, Q, K);
}
long long calculate(int ar, int ac, int br, int bc) {
return data.ask(ar, br, ac, bc);
}
