#include "game.h"
#include <algorithm>
using namespace std;
int N;
struct STUpdate{
int i; long long x;
STUpdate(int _i = -1, long long _x = -1) : i(_i), x(_x){};
};
struct STTUpdate{
int i; STUpdate u;
STTUpdate(int _i = -1, int _j = -1, long long _x = -1) : i(_i){
u = {_j, _x};
}
};
struct STQuery{
int l, r;
STQuery(int _l = -1, int _r = -1) : l(_l), r(_r){};
};
struct STTQuery{
int l, r; STQuery q;
STTQuery(int l1 = -1, int r1 = -1, int l2 = -1, int r2 = -1) : l(l1), r(r1){
q = {l2, r2};
}
};
template<typename T, typename UT, typename QT>
class SegmentTree{
private:
void update(T *curr, int l, int r, const UT &u){
if(l == r){
curr->update(u);
return;
}
int mit = (l + r) >> 1;
if(curr->ls == NULL){
curr->create_child();
}
if(u.i <= mit) update(curr->ls, l, mit, u);
else update(curr->rs, mit+1, r, u);
curr->merge(u);
}
long long query(T *curr, int l, int r, const QT &q){
if(l > q.r || r < q.l) return 0;
if(q.l <= l && r <= q.r) return curr->query(q);
int mit = (l + r) >> 1;
long long res = 0;
if(curr -> ls != NULL) res = __gcd(res, query(curr->ls, l, mit, q));
if(curr -> rs != NULL) res = __gcd(res, query(curr->rs, mit+1, r, q));
return res;
}
public:
T root;
void update(UT u){update(&root, 0, N-1, u);}
long long query(QT q){return query(&root, 0, N-1, q);}
};
struct STNode{
long long v;
STNode *ls, *rs;
STNode() : v(0), ls(NULL), rs(NULL){};
void create_child(){
ls = new STNode;
rs = new STNode;
}
void update(const STUpdate &u){v = u.x;}
long long query(const STQuery &q){return v;}
void merge(const STUpdate &u){v = __gcd(ls->v, rs->v);}
};
struct STTNode{
SegmentTree<STNode, STUpdate, STQuery> st;
STTNode *ls, *rs;
STTNode() : ls(NULL), rs(NULL){}
void create_child(){
ls = new STTNode;
rs = new STTNode;
}
void update(const STTUpdate &u){st.update(u.u);}
long long query(const STTQuery &q){return st.query(q.q);}
void merge(const STTUpdate &u){
long long q1 = ls->st.query({u.u.i, u.u.i});
long long q2 = rs->st.query({u.u.i, u.u.i});
st.update({u.u.i, __gcd(q1, q2)});
}
};
SegmentTree<STTNode, STTUpdate, STTQuery> ST;
void init(int R, int C){
N = max(R, C);
}
void update(int P, int Q, long long K) {
ST.update({P, Q, K});
}
long long calculate(int P, int Q, int U, int V) {
return ST.query({P, U, Q, V});
}
