#include <bits/stdc++.h>
#include "game.h"
using namespace std;
struct nodeY {
nodeY* l;
nodeY* r;
long long gcd;
nodeY() : l(nullptr), r(nullptr), gcd(0) {}
};
struct nodeX {
nodeY* root;
nodeX* l;
nodeX* r;
nodeX() : root(nullptr), l(nullptr), r(nullptr) {}
} *root;
int N, M;
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 updateY(nodeY* &x, int lx, int rx, int pos, long long v) {
if (!x) {
x = new nodeY();
}
if (lx == rx) {
x->gcd = v;
return;
}
int mid = (lx + rx) / 2;
if (pos <= mid) {
updateY(x->l, lx, mid, pos, v);
} else {
updateY(x->r, mid + 1, rx, pos, v);
}
if (x->l) {
x->gcd = x->l->gcd;
} else {
x->gcd = 0;
}
if (x->r) {
x->gcd = gcd2(x->gcd, x->r->gcd);
}
}
long long queryY(nodeY* &x, int lx, int rx, int st, int dr) {
if (!x) {
return 0;
}
if (st <= lx && rx <= dr) {
return x->gcd;
}
int mid = (lx + rx) / 2;
long long ans = 0;
if (st <= mid) {
ans = gcd2(ans, queryY(x->l, lx, mid, st, dr));
}
if (mid < dr) {
ans = gcd2(ans, queryY(x->r, mid + 1, rx, st, dr));
}
return ans;
}
void updateX(nodeX* &x, int lx, int rx, int X, int Y, long long v) {
if (!x) {
x = new nodeX();
}
if (lx == rx) {
updateY(x->root, 0, M - 1, Y, v);
return;
}
int mid = (lx + rx) / 2;
if (X <= mid) {
updateX(x->l, lx, mid, X, Y, v);
} else {
updateX(x->r, mid + 1, rx, X, Y, v);
}
int64_t gcd = 0;
if (x->l) {
gcd = queryY(x->l->root, 0, M - 1, Y, Y);
}
if (x->r) {
gcd = gcd2(gcd, queryY(x->r->root, 0, M - 1, Y, Y));
}
updateY(x->root, 0, M - 1, Y, gcd);
}
long long queryX(nodeX* &x, int lx, int rx, int x1, int x2, int y1, int y2) {
if (!x) {
return 0;
}
if (x1 <= lx && rx <= x2) {
return queryY(x->root, 0, M - 1, y1, y2);
}
int mid = (lx + rx) / 2;
long long ans = 0;
if (x1 <= mid) {
ans = gcd2(ans, queryX(x->l, lx, mid, x1, x2, y1, y2));
}
if (mid < x2) {
ans = gcd2(ans, queryX(x->r, mid + 1, rx, x1, x2, y1, y2));
}
return ans;
}
void init(int R, int C) {
N = R;
M = C;
}
void update(int P, int Q, long long K) {
updateX(root, 0, N - 1, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return queryX(root, 0, N - 1, P, U, Q, V);
}
