#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())
static char buf[200 << 20];
void* operator new(size_t s) {
static size_t i = sizeof buf; assert(s < i);
return (void*)&buf[i -= s];
}
void operator delete(void*) {}
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;
}
const int inf = 1e9+20;
struct lt {
lt *l=NULL, *r=NULL;
int p;
pi x;
ll c,g;
ll sx,ex;
lt () : p (rand()), x(-1,-1), c(0),g(0), sx(-1),ex(-1) {}
void upd() {
g = gcd(c,gcd(l ? l->g : 0, r ? r->g : 0));
sx=ex=x.f;
if (l) sx = l->sx;
if (r) ex = r->ex;
}
friend void split(lt *t, lt *&wl, lt *&wr, const pi &X) {
if (!t) {
wl=wr=NULL;
return;
}
if (t->x <= X) {
split(t->r,t->r,wr,X);
wl=t;
} else {
split(t->l,wl,t->l,X);
wr=t;
}
t->upd();
}
friend void merge(lt *tl, lt *tr, lt *&i) {
// cerr << "test4" << " " << tl << " " << tr << endl;
assert(tl != tr);
if (!tl || !tr) {
i = (tl ? tl : tr);
return;
}
if (tl->p < tr->p) {
merge(tl,tr->l,tr->l);
i=tr;
} else {
merge(tl->r,tr,tl->r);
i=tl;
}
i->upd();
}
static void op(lt *&root, const pi &X, ll val) {
// cerr << "test" << endl;
lt *lp=NULL,*rp=NULL;
split(root,root,rp,X);
split(root,lp,root,{X.f,X.s-1});
if (!root) {
root = new lt;
root->x=X;
root->upd();
}
root->g=root->c=val;
// cerr << "test3" << endl;
merge(lp,root,root);
merge(root,rp,root);
}
static ll q(lt *root, int xl, int xr) { // benq speedup -- no rewrite
if (!root) return 0;
if (root->ex < xl || root->sx > xr) return 0;
if (xl <= root->sx && root->ex <= xr) return root->g;
ll val = (root->x.f >= xl && root->x.f <= xr ? root->c : 0);
if (root->l) val=gcd(val,q(root->l,xl,xr));
if (root->r) val=gcd(val,q(root->r,xl,xr));
return val;
}
};
struct sstot {
sstot *l=NULL, *r=NULL;
int s,e;
lt *t;
sstot () {
t=new lt;
}
void op(const pi &X, ll val) {
// cerr << "test2 " << X.f << " " << X.s << " " << val << endl;
lt::op(t,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 lt::q(t,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({Q,P},K);
}
long long calculate(int P, int Q, int U, int V) {
return root.q(min(Q,V),max(Q,V),min(P,U),max(P,U));
}
