//gemini optimized memory
#include "game.h"
#include <algorithm>
using namespace std;
typedef long long ll;
ll gcd2(ll X, ll Y) {
while (Y) {
X %= Y;
swap(X, Y);
}
return X;
}
struct Node {
int l, r;
ll val;
};
// Global pools to stay under 250MB
// Inner nodes: ~6.5M * 24 bytes ≈ 156MB
// Outer nodes: ~45k * 24 bytes ≈ 1MB
Node tree_inner[6500000];
Node tree_outer[45000];
int inner_ptr = 1, outer_ptr = 1;
int outer_roots[45000]; // Maps outer node to its inner tree root
int R_max, C_max;
void update_inner(int &cur, int lo, int hi, int pos, ll val, bool leaf) {
if (!cur) cur = inner_ptr++;
if (lo == hi) {
tree_inner[cur].val = leaf ? val : val; // Logic handled by caller
return;
}
int mid = lo + (hi - lo) / 2;
if (pos <= mid) update_inner(tree_inner[cur].l, lo, mid, pos, val, leaf);
else update_inner(tree_inner[cur].r, mid + 1, hi, pos, val, leaf);
tree_inner[cur].val = gcd2(tree_inner[tree_inner[cur].l].val, tree_inner[tree_inner[cur].r].val);
}
ll query_inner(int cur, int lo, int hi, int ql, int qr) {
if (!cur || ql > hi || qr < lo) return 0;
if (ql <= lo && hi <= qr) return tree_inner[cur].val;
int mid = lo + (hi - lo) / 2;
return gcd2(query_inner(tree_inner[cur].l, lo, mid, ql, qr),
query_inner(tree_inner[cur].r, mid + 1, hi, ql, qr));
}
void update_outer(int &cur, int lo, int hi, int r, int c, ll val) {
if (!cur) cur = outer_ptr++;
if (lo != hi) {
int mid = lo + (hi - lo) / 2;
if (r <= mid) update_outer(tree_outer[cur].l, lo, mid, r, c, val);
else update_outer(tree_outer[cur].r, mid + 1, hi, r, c, val);
// Non-leaf: val is the GCD of children's results at column c
ll g1 = query_inner(outer_roots[tree_outer[cur].l], 0, C_max - 1, c, c);
ll g2 = query_inner(outer_roots[tree_outer[cur].r], 0, C_max - 1, c, c);
update_inner(outer_roots[cur], 0, C_max - 1, c, gcd2(g1, g2), false);
} else {
// Leaf: directly update the value
update_inner(outer_roots[cur], 0, C_max - 1, c, val, true);
}
}
ll query_outer(int cur, int lo, int hi, int r1, int r2, int c1, int c2) {
if (!cur || r1 > hi || r2 < lo) return 0;
if (r1 <= lo && hi <= r2) return query_inner(outer_roots[cur], 0, C_max - 1, c1, c2);
int mid = lo + (hi - lo) / 2;
return gcd2(query_outer(tree_outer[cur].l, lo, mid, r1, r2, c1, c2),
query_outer(tree_outer[cur].r, mid + 1, hi, r1, r2, c1, c2));
}
int root = 0;
void init(int R, int C) {
R_max = R; C_max = C;
}
void update(int P, int Q, ll K) {
update_outer(root, 0, R_max - 1, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
return query_outer(root, 0, R_max - 1, P, U, Q, V);
}
