#include "bits/stdc++.h"
#include "game.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll) a.size()
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = 1e9 + 5;
struct Node{
Node* lc;
Node* rc;
ll pri,sub,x,val;
Node(ll _x,ll _val){
lc = rc = NULL;
pri = rng();
x = _x, sub = val = _val;
}
};
inline ll get(Node* a){
if(!a) return 0;
return a -> sub;
}
inline void recalc(Node* a){
if(!a) return;
a -> sub = __gcd(a->val,__gcd(get(a->lc),get(a->rc)));
}
Node* merge(Node* a,Node* b){
recalc(a),recalc(b);
if(!a || !b) return (!a ? b : a);
if(a->pri > b->pri){
a -> rc = merge(a->rc,b);
recalc(a);
return a;
}
b -> lc = merge(a, b->lc);
recalc(b);
return b;
}
array<Node*,2> split(Node* a,ll c){
recalc(a);
if(!a) return {NULL, NULL};
if(a -> x < c){
auto xd = split(a -> rc, c);
a -> rc = xd[0];
recalc(a);
return {a,xd[1]};
}
auto xd = split(a -> lc, c);
a -> lc = xd[1];
recalc(a);
return {xd[0],a};
}
Node* del(Node* a, ll c){
recalc(a);
if(!a) return NULL;
auto xd = split(a, c);
auto xd2 = split(xd[1], c+1);
xd[0] = merge(xd[0], xd2[1]);
recalc(xd[0]);
return xd[0];
}
Node* ins(Node* a,Node* b){
recalc(a),recalc(b);
if(!a) return b;
auto xd = split(a,b->x);
xd[0] = merge(xd[0], b);
recalc(xd[0]);
xd[0] = merge(xd[0], xd[1]);
recalc(xd[0]);
return xd[0];
}
vector<array<ll,2>> v;
vector<Node*> T;
inline void add(ll x,ll y, ll k){
ll p = 0, l = 1, r = INF;
while(l <= r){
T[p] = del(T[p], y);
recalc(T[p]);
Node* cur = new Node(y, k);
T[p] = ins(T[p], cur);
recalc(T[p]);
if(l == r) return;
ll mid = (l+r)/2;
if(x <= mid){
if(v[p][0] == -1){
v[p][0] = sz(v);
v.push_back({-1,-1});
T.push_back(new Node(-1, 0));
}
p = v[p][0];
r = mid;
}
else{
if(v[p][1] == -1){
v[p][1] = sz(v);
v.push_back({-1,-1});
T.push_back(new Node(-1, 0));
}
p = v[p][1];
l = mid + 1;
}
}
}
ll query(ll rt,ll l,ll r,ll gl,ll gr,ll ql,ll qr){
if(r < gl || l > gr) return 0LL;
if(l >= gl && r <= gr){
auto xd = split(T[rt], ql);
auto xd2 = split(xd[1], qr+1);
ll res = get(xd2[0]);
xd[0] = merge(xd[0], xd2[0]);
recalc(xd[0]);
xd[0] = merge(xd[0], xd2[1]);
recalc(xd[0]);
T[rt] = xd[0];
return res;
}
ll mid = (l+r)/2, hm = 0;
if(v[rt][0] != -1) hm = __gcd(hm, query(v[rt][0],l,mid,gl,gr,ql,qr));
if(v[rt][1] != -1) hm = __gcd(hm, query(v[rt][1],mid+1,r,gl,gr,ql,qr));
return hm;
}
void init(int R, int C){
v.push_back({-1,-1});
T.push_back(new Node(-1, 0));
}
void update(int P, int Q, ll K){
P++,Q++;
add(P,Q,K);
}
ll calculate(int P, int Q, int U, int V){
P++,Q++,U++,V++;
return query(0,1,INF,P,U,Q,V);
}
