#include "game.h"
/**
* Author: Nicholas Winschel
* Created: 05.23.2023 20:57:47
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
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;
}
int inf = 1e9+20;
struct treap {
vi l,r,p;
V<pi> x;
vl c,g;
int root=0;
treap() : l(1),r(1),x(1),p(1),c(1),g(1) {}
void upd(int v) {
g[v] = c[v];
g[v] = gcd(g[v],g[l[v]]);
g[v] = gcd(g[v],g[r[v]]);
}
void split(int v, int &wl, int &wr, pi X) {
if (!v) {
wl=wr=0;
return;
}
if (x[v] <= X) {
split(r[v],r[v],wr,X);
wl=v;
} else {
split(l[v],wl,l[v],X);
wr=v;
}
upd(v);
}
void merge(int il, int ir, int &i) {
if (!il || !ir) {
i = (il ? il : ir);
return;
}
if (p[il] < p[ir]) {
merge(il,l[ir],l[ir]);
i=ir;
} else {
merge(r[il],ir,r[il]);
i=il;
}
upd(i);
}
void op(pi X, ll val) {
int lp=0,rp=0;
split(root,root,rp,X);
split(root,lp,root,{X.f,X.s-1});
if (!root) {
root = sz(l);
l.push_back(0);
r.push_back(0);
p.push_back(rand());
x.push_back(X);
c.push_back(val);
g.push_back(val);
}
c[root]=g[root]=val;
merge(lp,root,root);
merge(root,rp,root);
}
ll q(int xl, int xr) {
int lp=0,rp=0;
split(root,root,rp,{xr,inf});
split(root,lp,root,{xl,-inf});
ll ret = g[root];
merge(lp,root,root);
merge(root,rp,root);
return ret;
}
};
struct sstot {
sstot *l=NULL, *r=NULL;
int s,e;
treap t;
void op(pi X, ll val) {
t.op(X,val);
if (e-s <= 1) return;
int y = X.s;
int m = (s+e)>>1;
if (y < m) {
if (!l) l = new sstot;
l->s=s;
l->e=m;
l->op(X,val);
} else {
if (!r) r = new sstot;
r->s=m;
r->e=e;
r->op(X,val);
}
}
ll q(int xl, int xr, int yl, int yr) {
if (yl >= e || yr < s) return 0;
if (yl <= s && yr >= e-1) return t.q(xl,xr);
int m = (s+e)>>1;
return gcd((l ? l->q(xl,xr,yl,yr) : 0), (r ? r->q(xl,xr,yl,yr) : 0));
}
// ll q(int xl, int xr, int yl, int yr) {
// ll ans = _q(xl,xr,yl,yr);
// cerr << "dbg: y=[" << s << "," << e << "): " << "\n q=[" << xl << "," << xr << "]*["
// << yl << "," << yr << "]\n ans=" << ans << "\n";
// return ans;
// }
};
sstot root;
void init(int R, int C) {
root=sstot();
root.s=0;
root.e=inf;
}
void update(int P, int Q, long long K) {
root.op({P,Q},K);
}
long long calculate(int P, int Q, int U, int V) {
return root.q(min(P,U),max(P,U),min(Q,V),max(Q,V));
}
