#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);
map<int,int> treeV;
vector<Tree> tree(14'000'000); int nextfree = 1;
vector<Tree2> tree2(1'400'000); int nextfree2 = 1;
int R, C;
struct Tree {
int left, right; ll val;
Tree() : left(0), right(0), val(0) {}
void update(int v, int xl, int xr, ll delta) {
if (v < xl || v > xr) return;
if (xl == xr) {
val = delta;
} else {
int xm = (xl + xr) / 2;
if (v <= xm) {
if (!left) left = nextfree++;
tree[left].update(v, xl, xm, delta);
} else {
if (!right) right = nextfree++;
tree[right].update(v, xm+1, xr, delta);
}
val = 0;
if (left) val = gcd2(val, tree[left].val);
if (right) val = gcd2(val, tree[right].val);
}
}
ll query(int l, int r, int xl, int xr) {
if (l > r) return 0;
if (l == xl && r == xr) {
return val;
} else {
int xm = (xl + xr) / 2;
ll ans = 0;
if (left)
ans = gcd2(ans, tree[left].query(l, min(r, xm), xl, xm));
if (right)
ans = gcd2(ans, tree[right].query(max(l, xm+1), r, xm+1, xr));
return ans;
}
}
};
struct Tree2 {
int left, right, val;
Tree2() : left(0), right(0), val(0) {}
void update(int v, int w, int xl, int xr, ll delta) {
if (v < xl || v > xr) return;
ll delta2 = tree[treeV[w]].query(xl, xr, 0, R-1);
if (!val) val = nextfree++;
tree[val].update(w, 0, C-1, delta2);
if (xl != xr) {
int xm = (xl + xr) / 2;
if (v <= xm) {
if (!left) left = nextfree2++;
tree2[left].update(v, w, xl, xm, delta);
} else {
if (!right) right = nextfree2++;
tree2[right].update(v, w, xm+1, xr, delta);
}
}
}
ll query(int l, int r, int l2, int r2, int xl, int xr) {
if (l > r) return 0;
if (l == xl && r == xr) {
if (!val) return 0;
return tree[val].query(l2, r2, 0, C-1);
} else {
int xm = (xl + xr) / 2;
ll ans = 0;
if (left)
ans = gcd2(ans, tree2[left].query(l, min(r, xm), l2, r2, xl, xm));
if (right)
ans = gcd2(ans, tree2[right].query(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++;
tree[treeV[Q]].update(P, 0, R-1, K);
tree2[0].update(P, Q, 0, R-1, K);
}
long long calculate(int P, int Q, int U, int V) {
return tree2[0].query(P, U, Q, V, 0, R-1);
}
