#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int N, M;
struct NodeY{
long long val = 0;
NodeY *lptr_y = nullptr, *rptr_y = nullptr;
};
struct NodeX{
NodeX *lptr_x = nullptr, *rptr_x = nullptr;
NodeY *ptr_y = nullptr;
};
struct TwoDimSegTree{
NodeX *root;
long long query_y(NodeY *v, int tl, int tr, int ly, int ry){
if(!v || ly > ry) return 0;
else if(tl == ly && tr == ry) return v->val;
else{
int tm = tl + (tr - tl) / 2;
return __gcd(query_y(v->lptr_y, tl, tm, ly, min(ry, tm)), query_y(v->rptr_y, tm + 1, tr, max(ly, tm + 1), ry));
}
}
long long query_x(NodeX *v, int tl, int tr, int lx, int rx, int ly, int ry){
if(!v || lx > rx) return 0;
else if(tl == lx && tr == rx) return query_y(v->ptr_y, 0, M - 1, ly, ry);
else{
int tm = tl + (tr - tl) / 2;
return __gcd(query_x(v->lptr_x, tl, tm, lx, min(tm, rx), ly, ry), query_x(v->rptr_x, tm + 1, tr, max(lx, tm + 1), rx, ly, ry));
}
}
void update_y(NodeY *&v, int l, int r, int pos, long long val){
if(!v) v = new NodeY();
if(l == r) v->val = val;
else{
int m = l + (r - l) / 2;
if(pos <= m) update_y(v->lptr_y, l, m, pos, val);
else update_y(v->rptr_y, m + 1, r, pos, val);
v->val = __gcd(v->lptr_y ? v->lptr_y->val : 0, v->rptr_y ? v->rptr_y->val : 0);
}
}
void update_x(NodeX *&v, int l, int r, int posx, int posy, long long val){
if(!v) v = new NodeX();
if(l == r) update_y(v->ptr_y, 0, M - 1, posy, val);
else{
int m = l + (r - l) / 2;
if(posx <= m) update_x(v->lptr_x, l, m, posx, posy, val);
else update_x(v->rptr_x, m + 1, r, posx, posy, val);
val = __gcd(v->lptr_x ? query_y(v->lptr_x->ptr_y, 0, M - 1, posy, posy) : 0, v->rptr_x ? query_y(v->rptr_x->ptr_y, 0, M - 1, posy, posy) : 0);
update_y(v->ptr_y, 0, M - 1, posy, val);
}
}
};
TwoDimSegTree sgt;
void init(int R, int C){
N = R, M = C;
}
void update(int P, int Q, long long K) {
sgt.update_x(sgt.root, 0, N - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return sgt.query_x(sgt.root, 0, N - 1, P, U, Q, V);
}
