#include "game.h"
#define LG 30 /* LG = ceil(log2(10^9)) */
#define NU 22000
#define N (NU * (LG + 1))
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
int r, c;
long long xx[1 + N]; int ul[1 + N], ur[1 + N], dl[1 + N], dr[1 + N], t_, _ = 1;
void init(int R, int C) {
r = R, c = C;
}
int update_(int t, int il, int ir, int jl, int jr, int i, int j, long long x) {
if (t == 0)
t = _++;
if (ir - il == 1 && jr - jl == 1)
xx[t] = x;
else {
int im = (il + ir) / 2, jm = (jl + jr) / 2;
if (i < im && j < jm)
ul[t] = update_(ul[t], il, im, jl, jm, i, j, x);
else if (i < im && j >= jm)
ur[t] = update_(ur[t], il, im, jm, jr, i, j, x);
else if (i >= im && j < jm)
dl[t] = update_(dl[t], im, ir, jl, jm, i, j, x);
else
dr[t] = update_(dr[t], im, ir, jm, jr, i, j, x);
xx[t] = gcd(gcd(gcd(xx[ul[t]], xx[ur[t]]), xx[dl[t]]), xx[dr[t]]);
}
return t;
}
long long ans;
void query_(int t, int il, int ir, int jl, int jr, int i1, int i2, int j1, int j2) {
int im, jm;
if (i2 <= il || ir <= i1 || j2 <= jl || jr <= j1)
return;
if (i1 <= il && ir <= i2 && j1 <= jl && jr <= j2) {
ans = gcd(ans, xx[t]);
return;
}
im = (il + ir) / 2, jm = (jl + jr) / 2;
query_(ul[t], il, im, jl, jm, i1, i2, j1, j2);
query_(ur[t], il, im, jm, jr, i1, i2, j1, j2);
query_(dl[t], im, ir, jl, jm, i1, i2, j1, j2);
query_(dr[t], im, ir, jm, jr, i1, i2, j1, j2);
}
void update(int i, int j, long long x) {
t_ = update_(t_, 0, r, 0, c, i, j, x);
}
long long calculate(int i1, int j1, int i2, int j2) {
i2++, j2++;
ans = 0, query_(t_, 0, r, 0, c, i1, i2, j1, j2);
return ans;
}
