#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MXN = 2e3 + 5;
struct NodeY {
long long val = 0;
NodeY *left = nullptr, *right = nullptr;
};
struct NodeX {
NodeX *left = nullptr, *right = nullptr;
NodeY *treeY = nullptr;
};
int n, m;
// Update Y-axis segment tree
void updateY(NodeY* &node, int ly, int ry, int y, long long val) {
if (!node) node = new NodeY();
if (ly == ry) {
node->val = val;
return;
}
int my = (ly + ry) / 2;
if (y <= my) updateY(node->left, ly, my, y, val);
else updateY(node->right, my + 1, ry, y, val);
long long lv = node->left ? node->left->val : 0;
long long rv = node->right ? node->right->val : 0;
node->val = gcd(lv, rv);
}
// Update X-axis tree, propagating to Y
void updateX(NodeX* &node, int lx, int rx, int x, int y, long long val) {
if (!node) node = new NodeX();
updateY(node->treeY, 0, m - 1, y, val);
if (lx == rx) return;
int mx = (lx + rx) / 2;
if (x <= mx) updateX(node->left, lx, mx, x, y, val);
else updateX(node->right, mx + 1, rx, x, y, val);
}
// Query Y-tree
long long queryY(NodeY* node, int ly, int ry, int y1, int y2) {
if (!node || ry < y1 || ly > y2) return 0;
if (y1 <= ly && ry <= y2) return node->val;
int my = (ly + ry) / 2;
return gcd(
queryY(node->left, ly, my, y1, y2),
queryY(node->right, my + 1, ry, y1, y2)
);
}
// Query X-tree
long long queryX(NodeX* node, int lx, int rx, int x1, int x2, int y1, int y2) {
if (!node || rx < x1 || lx > x2) return 0;
if (x1 <= lx && rx <= x2) return queryY(node->treeY, 0, m - 1, y1, y2);
int mx = (lx + rx) / 2;
return gcd(
queryX(node->left, lx, mx, x1, x2, y1, y2),
queryX(node->right, mx + 1, rx, x1, x2, y1, y2)
);
}
NodeX *root = nullptr;
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);
}
