#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Inf = 1e9 + 3;
struct Seg {
ll g;
Seg *lc, *rc;
Seg (){
g = 0;
lc = NULL;
rc = NULL;
}
void Set(int idx, ll val, int L, int R){
if(L + 1 == R){
g = val;
return ;
}
int mid = (L + R) >> 1;
if(idx < mid){
if(!lc) lc = new Seg();
lc -> Set(idx, val, L, mid);
} else {
if(!rc) rc = new Seg();
rc -> Set(idx, val, mid, R);
}
g = __gcd(lc ? lc -> g : 0, rc ? rc -> g : 0);
}
ll Get(int l, int r, int L, int R){
if(r <= L || R <= l) return 0;
if(l <= L && R <= r) return g;
int mid = (L + R) >> 1;
return __gcd(lc ? lc -> Get(l, r, L, mid) : 0, rc ? rc -> Get(l, r, mid, R) : 0);
}
void Update(Seg *hl, Seg *hr, int idx, int L, int R){
if(L + 1 == R){
g = __gcd(hl ? hl -> g : 0, hr ? hr -> g : 0);
return ;
}
int mid = (L + R) >> 1;
if(idx < mid){
if(!lc) lc = new Seg();
lc -> Update(hl ? hl -> lc : NULL, hr ? hr -> lc : NULL, idx, L, mid);
} else {
if(!rc) rc = new Seg();
rc -> Update(hl ? hl -> rc : NULL, hr ? hr -> rc : NULL, idx, mid, R);
}
g = __gcd(lc ? lc -> g : 0, rc ? rc -> g : 0);
}
};
struct Seg2D {
Seg *ds;
Seg2D *lc, *rc;
Seg2D (){
ds = new Seg();
lc = NULL;
rc = NULL;
}
void Set(int x, int y, ll val, int L, int R){
if(L + 1 == R){
ds -> Set(y, val, 0, Inf);
return ;
}
int mid = (L + R) >> 1;
if(x < mid){
if(!lc) lc = new Seg2D();
lc -> Set(x, y, val, L, mid);
} else {
if(!rc) rc = new Seg2D();
rc -> Set(x, y, val, mid, R);
}
ds -> Update(lc ? lc -> ds : NULL, rc ? rc -> ds : NULL, y, 0, Inf);
}
ll Get(int lx, int rx, int ly, int ry, int L, int R){
if(rx <= L || R <= lx) return 0;
if(lx <= L && R <= rx) return ds -> Get(ly, ry, 0, Inf);
int mid = (L + R) >> 1;
return __gcd(lc ? lc -> Get(lx, rx, ly, ry, L, mid) : 0, rc ? rc -> Get(lx, rx, ly, ry, mid, R) : 0);
}
};
Seg2D Board;
void init(int R, int C) {
assert(R <= Inf);
assert(C <= Inf);
}
void update(int P, int Q, ll K) {
Board.Set(P, Q, K, 0, Inf);
}
ll calculate(int P, int Q, int U, int V) {
return Board.Get(P, U + 1, Q, V + 1, 0, Inf);
}
