#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
long long gcd2(long long X, long long Y);
const int N = 20'000'000;
int lptr[N], rptr[N]; ll val[N];
int nextfree = 1;
int R, C;
void update1(int idx, int v, int xl, int xr, ll delta) {
if (v < xl || v > xr) return;
if (xl == xr) {
val[idx] = delta;
} else {
int xm = (xl + xr) / 2;
if (v <= xm) {
if (!lptr[idx]) lptr[idx] = nextfree++;
update1(lptr[idx], v, xl, xm, delta);
} else {
if (!rptr[idx]) rptr[idx] = nextfree++;
update1(rptr[idx], v, xm+1, xr, delta);
}
val[idx] = 0;
if (lptr[idx]) val[idx] = gcd2(val[idx], val[lptr[idx]]);
if (rptr[idx]) val[idx] = gcd2(val[idx], val[rptr[idx]]);
}
}
ll query1(int idx, int l, int r, int xl, int xr) {
if (l > r) return 0;
if (l == xl && r == xr) {
return val[idx];
} else {
int xm = (xl + xr) / 2;
ll ans = 0;
if (lptr[idx]) ans = gcd2(ans, query1(lptr[idx], l, min(r, xm), xl, xm));
if (rptr[idx]) ans = gcd2(ans, query1(rptr[idx], max(l, xm+1), r, xm+1, xr));
return ans;
}
}
void update2(int idx, int v, int w, int xl, int xr, ll delta) {
if (v < xl || v > xr) return;
if (xl != xr) {
int xm = (xl + xr) / 2;
if (v <= xm) {
if (!lptr[idx]) lptr[idx] = nextfree++;
update2(lptr[idx], v, w, xl, xm, delta);
} else {
if (!rptr[idx]) rptr[idx] = nextfree++;
update2(rptr[idx], v, w, xm+1, xr, delta);
}
}
ll delta2 = delta;
if (lptr[idx]) delta2 = gcd2(delta2, query1(val[lptr[idx]], w, w, 1, C));
if (rptr[idx]) delta2 = gcd2(delta2, query1(val[rptr[idx]], w, w, 1, C));
if (!val[idx]) val[idx] = nextfree++;
update1(val[idx], w, 1, C, delta2);
}
ll query2(int idx, int l, int r, int l2, int r2, int xl, int xr) {
if (l > r) return 0;
if (l == xl && r == xr) {
if (!val[idx]) return 0;
return query1(val[idx], l2, r2, 1, C);
} else {
int xm = (xl + xr) / 2;
ll ans = 0;
if (lptr[idx]) ans = gcd2(ans, query2(lptr[idx], l, min(r, xm), l2, r2, xl, xm));
if (rptr[idx]) ans = gcd2(ans, query2(rptr[idx], max(l, xm+1), r, l2, r2, xm+1, xr));
return ans;
}
}
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void init(int _R, int _C) {
R = _R;
C = _C;
}
void update(int P, int Q, long long K) {
update2(0, P+1, Q+1, 1, R, K);
}
long long calculate(int P, int Q, int U, int V) {
return query2(0, P+1, U+1, Q+1, V+1, 1, R);
}
