#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Inf = 1e9 + 3;
const int LG = 30;
const int MX = 10010;
const int CNT = 198e5;
//int lc[CNT], rc[CNT]
int la = 1;
ll g[CNT];
int sn[CNT];
int ty;
int GetL(int id){
ty = sn[id] & 7;
if(ty == 0) return 0;
if(ty == 1) return 0;
if(ty == 2) return id + 1;
if(ty == 3) return id + 1;
if(ty == 4) return sn[id] >> 3;
return -1;
}
int GetR(int id){
ty = sn[id] & 7;
if(ty == 0) return 0;
if(ty == 1) return id + 1;
if(ty == 2) return 0;
if(ty == 3) return sn[id] >> 3;
if(ty == 4) return id + 1;
return -1;
}
void AddL(int id){
ty = sn[id] & 7;
if(ty >= 2) assert(false);
if(ty == 0) ++la, sn[id] = 2;
else sn[id] = 4 + (++ la) * 8;
}
void AddR(int id){
ty = sn[id] & 7;
if(ty == 1 || ty == 3 || ty == 4) assert(false);
if(ty == 0) ++la, sn[id] = 1;
else sn[id] = 3 + (++ la) * 8;
}
void Set(int id, int idx, ll val, int L, int R){
if(L + 1 == R){
g[id] = val;
return ;
}
int mid = (L + R) >> 1;
if(idx < mid){
if(!GetL(id)) AddL(id); //lc[id] = ++la;
Set(GetL(id), idx, val, L, mid);
} else {
if(!GetR(id)) AddR(id); //rc[id] = ++la;
Set(GetR(id), idx, val, mid, R);
}
g[id] = __gcd(g[GetL(id)], g[GetR(id)]);
}
ll Get(int id, int l, int r, int L, int R){
if(r <= L || R <= l) return 0;
if(l <= L && R <= r) return g[id];
int mid = (L + R) >> 1;
return __gcd(GetL(id) ? Get(GetL(id), l, r, L, mid) : 0, GetR(id) ? Get(GetR(id), l, r, mid, R) : 0);
}
void Update(int id, int hl, int hr, int idx, int L, int R){
if(L + 1 == R){
g[id] = __gcd(g[hl], g[hr]);
return ;
}
int mid = (L + R) >> 1;
if(idx < mid){
if(!GetL(id)) AddL(id);//lc[id] = ++la;
Update(GetL(id), GetL(hl), GetL(hr), idx, L, mid);
} else {
if(!GetR(id)) AddR(id);//rc[id] = ++la;
Update(GetR(id), GetR(hl), GetR(hr), idx, mid, R);
}
g[id] = __gcd(g[GetL(id)], g[GetR(id)]);
}
//Seg node[MX * LOG];
struct Seg2D {
int ds;
Seg2D *Lc, *Rc;
Seg2D (){
ds = 0;
Lc = NULL;
Rc = NULL;
}
void Set2D(int x, int y, ll val, int L, int R){
if(L + 1 == R){
if(!ds) ds = ++la;
Set(ds, y, val, 0, Inf);
return ;
}
int mid = (L + R) >> 1;
if(x < mid){
if(!Lc) Lc = new Seg2D();
Lc -> Set2D(x, y, val, L, mid);
} else {
if(!Rc) Rc = new Seg2D();
Rc -> Set2D(x, y, val, mid, R);
}
if(!ds) ds = ++la;
Update(ds, Lc ? Lc -> ds : 0, Rc ? Rc -> ds : 0, y, 0, Inf);
}
ll Get2D(int lx, int rx, int ly, int ry, int L, int R){
if(rx <= L || R <= lx) return 0;
if(lx <= L && R <= rx){
if(ds == 0) return 0;
return Get(ds, ly, ry, 0, Inf);
}
int mid = (L + R) >> 1;
return __gcd(Lc ? Lc -> Get2D(lx, rx, ly, ry, L, mid) : 0, Rc ? Rc -> Get2D(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.Set2D(P, Q, K, 0, Inf);
}
ll calculate(int P, int Q, int U, int V) {
return Board.Get2D(P, U + 1, Q, V + 1, 0, Inf);
}
