#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;
Node *l;
Node *r;
Node (){
val=0;
l=nullptr;
r=nullptr;
}
};
struct SegmentTree{
Node *root;
SegmentTree *l;
SegmentTree *r;
SegmentTree(){
root=new Node();
l=nullptr;
r=nullptr;
}
void update(Node *t, Node *tl, Node *tr, int l, int r, int pos, long long val, bool sussy){
if (l==r){
if (sussy) t->val=gcd2(tl?tl->val:0, tr?tr->val:0);
else t->val=val;
return;
}
if (!t->l) t->l=new Node();
if (!t->r) t->r=new Node();
int mid=(l+r)>>1;
if (pos<=mid) update(t->l, tl?tl->l:nullptr, tr?tr->l:nullptr, l, mid, pos, val, sussy);
else update(t->r, tl?tl->r:nullptr, tr?tr->r:nullptr, mid+1, r, pos, val, sussy);
t->val=gcd2(t->l->val, t->r->val);
}
long long get(Node *t, int l, int r, int L, int R){
if (r<L || R<l) return 0;
if (L<=l && r<=R) return t->val;
if (!t->l || !t->r) return 0;
int mid=(l+r)>>1;
return gcd2(get(t->l, l, mid, L, R), get(t->r, mid+1, r, L, R));
}
};
struct SegmentTree2d{
SegmentTree *root;
SegmentTree2d(){
root=new SegmentTree();
}
void update(SegmentTree *t, int l, int r, int x, int y, long long val){
if (l!=r){
int mid=(l+r)>>1;
if (!t->l) t->l=new SegmentTree();
if (!t->r) t->r=new SegmentTree();
if (x<=mid) update(t->l, l, mid, x, y, val);
else update(t->r, mid+1, r, x, y, val);
}
t->update(t->root, t->l?t->l->root:nullptr, t->r?t->r->root:nullptr, 1, C, y, val, l!=r);
}
long long get(SegmentTree *t, 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 t->get(t->root, 1, C, ly, ry);
if (!t->l || !t->r) return 0;
int mid=(l+r)>>1;
return gcd2(get(t->l, l, mid, lx, rx, ly, ry), get(t->r, mid+1, r, lx, rx, ly, ry));
}
} st;
void init(int _R, int _C) {
R=_R; C=_C;
}
void update(int P, int Q, long long K) {
++P; ++Q;
st.update(st.root, 1, R, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
++P; ++Q; ++U; ++V;
return st.get(st.root, 1, R, P, U, Q, V);
}
