#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct node_y {
map<int, long long> vals;
};
node_y* update_y(node_y *u, int y, long long val) {
if (!u) {
u = new node_y();
}
u->vals[y] = val;
return u;
}
long long get_y(node_y *u, int ly, int ry) {
if (!u) {
return 0LL;
}
long long res = 0;
for (auto [y, val]: u->vals) {
if (ly <= y && y <= ry) {
res = __gcd(res, val);
}
}
return res;
}
struct node_x {
node_y *root_y;
node_x *lch;
node_x *rch;
node_x(): root_y(nullptr), lch(nullptr), rch(nullptr) {};
};
node_x* update_x(node_x *u, int lt, int rt, int x, int y, long long val) {
if (!u) {
u = new node_x();
}
u->root_y = update_y(u->root_y, y, val);
if (lt == rt) {
return u;
}
int mt = (lt + rt) >> 1;
if (x <= mt) {
u->lch = update_x(u->lch, lt, mt, x, y, val);
}
else {
u->rch = update_x(u->rch, mt + 1, rt, x, y, val);
}
return u;
};
long long get_x(node_x *u, int lt, int rt, int lx, int rx, int ly, int ry) {
if (!u) {
return 0LL;
}
if (lt == lx && rt == rx) {
return get_y(u->root_y, ly, ry);
}
int mt = (lt + rt) >> 1;
if (rx <= mt) {
return get_x(u->lch, lt, mt, lx, rx, ly, ry);
}
else if (lx >= mt + 1) {
return get_x(u->rch, mt + 1, rt, lx, rx, ly, ry);
}
else {
return __gcd(get_x(u->lch, lt, mt, lx, mt, ly, ry), get_x(u->rch, mt + 1, rt, mt + 1, rx, ly, ry));
}
}
int n, m;
node_x *root_x = nullptr;
void init(int _n, int _m) {
n = _n;
m = _m;
}
void update(int x, int y, long long val) {
x++;
y++;
root_x = update_x(root_x, 1, n, x, y, val);
}
long long calculate(int lx, int ly, int rx, int ry) {
lx++;
ly++;
rx++;
ry++;
return get_x(root_x, 1, n, lx, rx, ly, ry);
}
