#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 SegmentTree{
public:
static const int maxv = 2e7 + 5;
static const int siz = 1000000000;
int tot, r;
int ls[maxv], rs[maxv], rt[maxv];
ll dat[maxv];
inline void init(){ r = 0, tot = 1; return; }
inline void update2(int q, ll k, int &u, int l = 0, int r = siz - 1){
if(!u)
u = tot++, dat[u] = 0;
//printf("update2 u = %d l = %d r = %d\n", u, l, r);
if(l == r){
dat[u] = k;
return;
}
int md = l + r >> 1;
if(q <= md)
update2(q, k, ls[u], l, md);
else
update2(q, k, rs[u], md + 1, r);
dat[u] = gcd2(dat[ls[u]], dat[rs[u]]);
return;
}
inline void pushUp(int q, int &v, int vl, int vr, int l = 0, int r = siz - 1){
if(!v)
v = tot++, dat[v] = 0;
if(l == r){
dat[v] = gcd2(dat[vl], dat[vr]);
return;
}
int md = l + r >> 1;
if(q <= md)
pushUp(q, ls[v], ls[vl], ls[vr], l, md);
else
pushUp(q, rs[v], rs[vl], rs[vr], md + 1, r);
dat[v] = gcd2(dat[ls[v]], dat[rs[v]]);
return;
}
inline void update(int p, int q, ll k, int &u, int l = 0, int r = siz - 1){
if(!u)
u = tot++, dat[u] = 0;
//printf("update u = %d rt = %d\n", u, rt[u]);
if(l == r){
update2(q, k, rt[u]);
return;
}
int md = l + r >> 1;
if(p <= md)
update(p, q, k, ls[u], l, md);
else
update(p, q, k, rs[u], md + 1, r);
pushUp(q, rt[u], rt[ls[u]], rt[rs[u]]);
return;
}
inline ll query2(int s, int t, int u, int l = 0, int r = siz - 1){
//printf("query2 u = %d\n", u);
if(!u){
return 0;
}
if(l >= s && r <= t){
return dat[u];
}
int md = l + r >> 1;
if(s > md)
return query2(s, t, rs[u], md + 1, r);
if(t <= md)
return query2(s, t, ls[u], l, md);
return gcd2(query2(s, t, ls[u], l, md), query2(s, t, rs[u], md + 1, r));
}
inline ll query(int p, int q, int s, int t, int u, int l = 0, int r = siz - 1){
if(!u)
return 0;
if(l >= p && r <= q)
return query2(s, t, rt[u]);
int md = l + r >> 1;
if(p > md)
return query(p, q, s, t, rs[u], md + 1, r);
if(q <= md)
return query(p, q, s, t, ls[u], l, md);
return gcd2(query(p, q, s, t, rs[u], md + 1, r), query(p, q, s, t, ls[u], 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);
}
