#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
using T = long long;
const T default_val = 0;
struct NodeY {
NodeY *l = nullptr, *r = nullptr;
T val = default_val;
};
struct NodeX {
NodeX *l = nullptr, *r = nullptr;
NodeY *st = nullptr;
};
struct ImplicitSegTree2D {
int x_min, x_max, y_min, y_max;
NodeX *root = nullptr;
ImplicitSegTree2D(): x_min(0), x_max(0), root(nullptr) {}
ImplicitSegTree2D(int _x_min, int _x_max, int _y_min, int _y_max) : x_min(_x_min), x_max(_x_max), y_min(_y_min), y_max(_y_max) {}
void updateY(NodeY *&node, int ly, int ry, int y, const T &v) {
if(!node) node = new NodeY();
if(ly == ry) {
node->val = v;
return;
}
int mid = ly + (ry - ly) / 2;
if(y <= mid) updateY(node->l, ly, mid, y, v);
else updateY(node->r, mid + 1, ry, y, v);
T lv = node->l ? node->l->val : default_val;
T rv = node->r ? node->r->val : default_val;
node->val = gcd2(lv, rv);
}
void updateX(NodeX *&node, int lx, int rx, int x, int y, const T &v) {
if(!node) node = new NodeX();
updateY(node->st, y_min, y_max, y, v);
if(lx == rx) return;
int mid = lx + (rx - lx) / 2;
if(x <= mid) updateX(node->l, lx, mid, x, y, v);
else updateX(node->r, mid + 1, rx, x, y, v);
}
void update(int x, int y, const T &v) {
if(x < x_min || x > x_max || y < y_min || y > y_max) return;
updateX(root, x_min, x_max, x, y, v);
}
T queryY(NodeY *node, int ly, int ry, int ql, int qr) const {
if(!node || qr < ly || ry < ql) return default_val;
if(ql <= ly && ry <= qr) return node->val;
int mid = ly + (ry - ly) / 2;
return gcd2(queryY(node->l, ly, mid, ql, qr), queryY(node->r, mid + 1, ry, ql, qr));
}
T queryX(NodeX *node, int lx, int rx, int qx1, int qx2, int qy1, int qy2) const {
if(!node || qx2 < lx || rx < qx1) return default_val;
if(qx1 <= lx && rx <= qx2) return queryY(node->st, y_min, y_max, qy1, qy2);
int mid = lx + (rx - lx) / 2;
return gcd2(queryX(node->l, lx, mid, qx1, qx2, qy1, qy2), queryX(node->r, mid + 1, rx, qx1, qx2, qy1, qy2));
}
T query(int x1, int y1, int x2, int y2) const {
if(x2 < x_min || x_max < x1 || y2 < y_min || y_max < y1) return default_val;
x1 = max(x1, x_min); x2 = min(x2, x_max);
y1 = max(y1, y_min); y2 = min(y2, y_max);
return queryX(root, x_min, x_max, x1, x2, y1, y2);
}
};
ImplicitSegTree2D st;
void init(int R, int C) {
st.x_min = 0;
st.x_max = R - 1;
st.y_min = 0;
st.y_max = C - 1;
}
void update(int P, int Q, long long K) {
st.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return st.query(P, Q, U, V);
}
