#include "game.h"
#include <bits/stdc++.h>
typedef long long ll;
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 SHIT{
public:
SHIT *ls, *rs;
ll dat;
SHIT(): ls(NULL), rs(NULL){}
} ;
class FUCK{
public:
FUCK *ls, *rs;
SHIT *rt;
FUCK(): ls(NULL), rs(NULL), rt(NULL){}
} ;
class SegmentTree{
public:
static const int maxv = 5e6 + 5;
static const int maxv2 = 1e7 + 5;
static const int siz = 1000000000;
FUCK *r;
inline void init(){ r = NULL; return; }
inline void update2(int q, ll k, SHIT *&u, int l = 0, int r = siz - 1){
if(u == NULL)
u = new SHIT();
//printf("update2 u = %d l = %d r = %d\n", u, l, r);
if(l == r){
u -> dat = k;
return;
}
int md = l + r >> 1;
SHIT *&ps = u -> ls, *&qs = u -> rs;
if(q <= md)
update2(q, k, ps, l, md);
else
update2(q, k, qs, md + 1, r);
u -> dat = gcd2(ps == NULL ? 0 : ps -> dat, qs == NULL ? 0 : qs -> dat);
return;
}
inline void pushUp(int q, SHIT *&v, SHIT *vl, SHIT *vr, int l = 0, int r = siz - 1){
if(vl == NULL && vr == NULL)
return;
if(v == NULL)
v = new SHIT();
if(l == r){
v -> dat = gcd2(vl != NULL ? vl -> dat : 0, vr != NULL ? vr -> dat : 0);
return;
}
int md = l + r >> 1;
SHIT *&ps = v -> ls, *&qs = v -> rs;
if(q <= md)
pushUp(q, ps, vl == NULL ? NULL : vl -> ls, vr == NULL ? NULL : vr -> ls, l, md);
else
pushUp(q, qs, vl == NULL ? NULL : vl -> rs, vr == NULL ? NULL : vr -> rs, md + 1, r);
v -> dat = gcd2(ps == NULL ? 0 : ps -> dat, qs == NULL ? 0 : qs -> dat);
return;
}
inline void update(int p, int q, ll k, FUCK *&u, int l = 0, int r = siz - 1){
if(u == NULL)
u = new FUCK();
//printf("update u = %d rt = %d\n", u, rt[u]);
if(l == r){
update2(q, k, u -> rt);
return;
}
int md = l + r >> 1;
FUCK *&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);
pushUp(q, u -> rt, ps == NULL ? NULL : ps -> rt, qs == NULL ? NULL : qs -> rt);
return;
}
inline ll query2(int s, int t, SHIT *&u, int l = 0, int r = siz - 1){
//printf("query2 u = %d\n", u);
if(u == NULL){
return 0;
}
if(l >= s && r <= t){
return u -> dat;
}
int md = l + r >> 1;
if(s > md)
return query2(s, t, u -> rs, md + 1, r);
if(t <= md)
return query2(s, t, u -> ls, l, md);
return gcd2(query2(s, t, u -> ls, l, md), query2(s, t, u -> rs, md + 1, r));
}
inline ll query(int p, int q, int s, int t, FUCK *&u, int l = 0, int r = siz - 1){
if(u == NULL)
return 0;
if(l >= p && r <= q)
return query2(s, t, u -> rt);
int md = l + r >> 1;
if(p > md)
return query(p, q, s, t, u -> rs, md + 1, r);
if(q <= md)
return query(p, q, s, t, u -> ls, l, md);
return gcd2(query(p, q, s, t, u -> rs, md + 1, r), query(p, q, s, t, u -> ls, l, md));
}
} 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);
}
