#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
struct Tree;
struct Tree2;
long long gcd2(long long X, long long Y);
const int N = 15'000'000;
map<int,int> treeV;
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)
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;
ll delta2 = query1(treeV[w], xl, xr, 0, R-1);
if (!val[idx]) val[idx] = nextfree++;
update1(val[idx], w, 0, C-1, delta2);
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 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, 0, C-1);
} 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) {
if (treeV.count(Q) == 0) treeV[Q] = nextfree++;
update1(treeV[Q], P, 0, R-1, K);
update2(0, P, Q, 0, R-1, K);
}
long long calculate(int P, int Q, int U, int V) {
return query2(0, P, U, Q, V, 0, R-1);
}
