#include "game.h"
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;
}
#include <bits/stdc++.h>
using namespace std;
int R, C;
struct Node{
long long val;
int il, ir;
Node (){
val=0;
il=0, ir=0;
}
};
struct SegmentTree{
vector<Node> t;
int il, ir;
SegmentTree(){
t.emplace_back();
il=0, ir=0;
}
};
struct SegmentTree2d{
vector<SegmentTree> t;
SegmentTree2d(){
t.emplace_back();
}
void update1(int k, int l, int r, int x, int y, long long val){
if (l!=r){
int mid=(l+r)>>1;
if (x<=mid){
if (!t[k].il){
t[k].il=t.size();
t.emplace_back();
}
update1(t[k].il, l, mid, x, y, val);
}else{
if (!t[k].ir){
t[k].ir=t.size();
t.emplace_back();
}
update1(t[k].ir, mid+1, r, x, y, val);
}
}
update2(k, 0, 1, 1e9, y, val, l!=r);
}
long long get1(int k, int l, int r, int lx, int rx, int ly, int ry){
if (rx<l || r<lx) return 0;
if (lx<=l && r<=rx) return get2(k, 0, 1, 1e9, ly, ry);
int mid=(l+r)>>1;
return gcd2(t[k].il?get1(t[k].il, l, mid, lx, rx, ly, ry):0, t[k].ir?get1(t[k].ir, mid+1, r, lx, rx, ly, ry):0);
}
void update2(int id, int k, int l, int r, int pos, long long val, bool sussy){
if (l==r){
if (sussy) t[id].t[k].val=gcd2(t[id].il?get2(t[id].il, 0, 1, 1e9, pos, pos):0, t[id].ir?get2(t[id].ir, 0, 1, 1e9, pos, pos):0);
else t[id].t[k].val=val;
return;
}
int mid=(l+r)>>1;
if (pos<=mid){
if (!t[id].t[k].il){
t[id].t[k].il=t[id].t.size();
t[id].t.emplace_back();
}
update2(id, t[id].t[k].il, l, mid, pos, val, sussy);
}else{
if (!t[id].t[k].ir){
t[id].t[k].ir=t[id].t.size();
t[id].t.emplace_back();
}
update2(id, t[id].t[k].ir, mid+1, r, pos, val, sussy);
}
t[id].t[k].val=gcd2(t[id].t[k].il?t[id].t[t[id].t[k].il].val:0, t[id].t[k].ir?t[id].t[t[id].t[k].ir].val:0);
}
long long get2(int id, int k, int l, int r, int L, int R){
if (r<L || R<l) return 0;
if (L<=l && r<=R) return t[id].t[k].val;
int mid=(l+r)>>1;
return gcd2(t[id].t[k].il?get2(id, t[id].t[k].il, l, mid, L, R):0, t[id].t[k].ir?get2(id, t[id].t[k].ir, mid+1, r, L, R):0);
}
} st;
void init(int _R, int _C) {
R=_R; C=_C;
}
void update(int P, int Q, long long K) {
++P; ++Q;
st.update1(0, 1, 1e9, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
++P; ++Q; ++U; ++V;
return st.get1(0, 1, 1e9, P, U, Q, V);
}
