#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
mt19937 rnd(2226701);
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;
}
class SegmentTree{
public:
static const int siz = 1000000000;
class Trp{
public:
Trp *ls, *rs;
int pos, fix;
ll k, g;
Trp(ll k_, ll pos_): k(k_), g(k_), pos(pos_), fix(rnd()){}
} ;
class Seg{
public:
Seg *ls, *rs;
Trp *rt;
Seg(): ls(NULL), rs(NULL), rt(NULL){}
} *r;
inline void init(){ r = NULL; return; }
inline void pushUp(Trp *&u){
Trp *ps = u -> ls, *qs = u -> rs;
u -> g = u -> k;
u -> g = gcd2(u -> g, ps == NULL ? 0 : ps -> g);
u -> g = gcd2(u -> g, qs == NULL ? 0 : qs -> g);
return;
}
inline void split(Trp *u, Trp *&x, Trp *&y, int q){ // <= q in x
if(u == NULL)
return void(x = y = NULL);
if(u -> pos <= q)
split(u -> rs, u -> rs, y, q), x = u;
else
split(u -> ls, x, u -> ls, q), y = u;
pushUp(u);
return;
}
inline void merge(Trp *&u, Trp *x, Trp *y){
if(x == NULL || y == NULL)
return (void)(u = (x == NULL ? y : x));
if(x -> fix < y -> fix)
merge(y -> ls, x, y -> ls), u = y;
else
merge(x -> rs, x -> rs, y), u = x;
pushUp(u);
return;
}
inline void update2(Trp *&u, int q, long long k){
Trp *x, *y, *z;
split(u, x, z, q - 1);
split(z, y, z, q);
delete(y);
y = new Trp(k, q);
merge(u, x, y);
merge(u, u, z);
return;
}
inline ll query2(Trp *&u, int s, int t){
Trp *x, *y, *z;
split(u, x, y, s - 1);
split(y, y, z, t);
ll ret = y == NULL ? 0 : y -> g;
merge(u, x, y);
merge(u, u, z);
return ret;
}
inline void update(int p, int q, ll k, Seg *&u, int l = 0, int r = siz - 1){
if(u == NULL)
u = new Seg();
if(l == r){
update2(u -> rt, q, k);
return;
}
int md = l + r >> 1;
Seg *&ps = u -> ls, *&qs = u -> rs;
if(p <= md)
update(p, q, k, ps, l, md);
else
update(p, q, k, qs, md + 1, r);
update2(u -> rt, q, gcd2(ps == NULL ? 0 : query2(ps -> rt, q, q), qs == NULL ? 0 : query2(qs -> rt, q, q)));
return;
}
inline ll query(int p, int q, int s, int t, Seg *&u, int l = 0, int r = siz - 1){
if(u == NULL)
return 0;
if(l >= p && r <= q)
return query2(u -> rt, s, t);
int md = l + r >> 1;
if(p > md)
return query(p, q, s, t, u -> rs, md + 1, r);
else if(q <= md)
return query(p, q, s, t, u -> ls, l, md);
return gcd2(query(p, q, s, t, u -> ls, l, md), query(p, q, s, t, u -> rs, md + 1, r));
}
} seg;
void init(int R, int C) {
seg.init();
}
void update(int P, int Q, long long K) {
seg.update(P, Q, K, seg.r);
return;
}
long long calculate(int P, int Q, int U, int V) {
return seg.query(P, U, Q, V, seg.r);
}
