#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int gapcnt, R, C;
#pragma pack(4)
struct YNode {
ll gap;
int lf = -1, rg = -1, lazy = -1;
} gap[10010010], trash;
inline ll _gcd(ll x, ll y) { if(x == 0 || y == 0) return x+y; return __gcd(x, y); }
ll queryY(int now, int s, int e, int si, int ei) {
if(s > ei || e < si) return 0;
if(gap[now].lazy > 0) {
if(gap[now].lazy >= si && gap[now].lazy <= ei) return gap[now].gap;
else return 0;
}
if(s >= si && e <= ei) return gap[now].gap;
ll lv = 0, rv = 0, ret = 0, m = s+e>>1;
if(gap[now].lf != -1) lv = queryY(gap[now].lf, s, m, si, ei);
if(gap[now].rg != -1) rv = queryY(gap[now].rg, m+1, e, si, ei);
return _gcd(ret, _gcd(lv, rv));
}
ll queryX(int n, int s, int e, int si, int ei, int ssi, int eei) {
if(s > ei || e < si) return 0;
if(s >= si && e <= ei) return queryY(gap[n].lazy, 1, C, ssi, eei);
ll lv = 0, rv = 0, m = s+e>>1;
if(gap[n].lf != -1) lv = queryX(gap[n].lf, s, m, si, ei, ssi, eei);
if(gap[n].rg != -1) rv = queryX(gap[n].rg, m+1, e, si, ei, ssi, eei);
return _gcd(lv, rv);
}
void updateY(int now, int s, int e, int si, int ei, ll v) {
if(s > ei || e < si) return;
if(s >= si && e <= ei) { gap[now].gap = v; return; }
if(gap[now].lazy == -1) {
gap[now].lazy = si; gap[now].gap = v; return;
} else {
int m = s+e>>1;
if(gap[now].lazy != -2) {
if(gap[now].lazy <= m) {
if(gap[now].lf == -1) gap[now].lf = gapcnt++;
updateY(gap[now].lf, s, m, gap[now].lazy, gap[now].lazy, gap[now].gap);
} else {
if(gap[now].rg == -1) gap[now].rg = gapcnt++;
updateY(gap[now].rg, m+1, e, gap[now].lazy, gap[now].lazy, gap[now].gap);
}
}
if(si <= m) {
if(gap[now].lf == -1) gap[now].lf = gapcnt++;
updateY(gap[now].lf, s, m, si, ei, v);
} else {
if(gap[now].rg == -1) gap[now].rg = gapcnt++;
updateY(gap[now].rg, m+1, e, si, ei, v);
}
ll lv = gap[now].lf == -1 ? 0 : gap[gap[now].lf].gap, rv = gap[now].rg == -1 ? 0 : gap[gap[now].rg].gap;
gap[now].gap = _gcd(lv, rv);
gap[now].lazy = -2;
}
}
void updateX(int now, int s, int e, int si, int ei, int v, ll z) {
if(s > ei || e < si) return;
if(gap[now].lazy < 0) gap[now].lazy = gapcnt++;
if(s >= si && e <= ei) { updateY(gap[now].lazy, 1, C, v, v, z); return; }
int m = s+e>>1;
if(si <= m) {
if(gap[now].lf == -1) gap[now].lf = gapcnt++;
updateX(gap[now].lf, s, m, si, ei, v, z);
} else {
if(gap[now].rg == -1) gap[now].rg = gapcnt++;
updateX(gap[now].rg, m+1, e, si, ei, v, z);
}
ll lv = gap[now].lf < 0 ? 0 : queryY(gap[gap[now].lf].lazy, 1, C, v, v),
rv = gap[now].rg < 0 ? 0 : queryY(gap[gap[now].rg].lazy, 1, C, v, v);
updateY(gap[now].lazy, 1, C, v, v, _gcd(lv, rv));
}
void init(int _R, int _C) {
gapcnt = 1; R = _R, C = _C;
}
void update(int P, int Q, ll K) {
++P; ++Q;
updateX(0, 1, R, P, P, Q, K);
if(gapcnt > 10000000) exit(1);
}
ll calculate(int P, int Q, int U, int V) {
++P; ++Q; ++U; ++V;
return queryX(0, 1, R, P, U, Q, V);
}
