#include "game.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 gen(69420);
struct node_y {
unsigned long long w;
pair<int, int> pos;
long long val;
node_y *lch;
node_y *rch;
int sz;
long long g;
node_y(pair<int, int> _pos, long long _val): w(gen()), pos(_pos), val(_val), lch(nullptr), rch(nullptr), sz(1), g(val) {};
};
void fix(node_y *u) {
u->sz = 1;
u->g = u->val;
for (auto v: {u->lch, u->rch}) {
if (v) {
u->sz += v->sz;
u->g = __gcd(u->g, v->g);
}
}
}
node_y* merge(node_y *lu, node_y *ru) {
if (!lu) {
return ru;
}
if (!ru) {
return lu;
}
if (lu->w > ru->w) {
lu->rch = merge(lu->rch, ru);
fix(lu);
return lu;
}
else {
ru->lch = merge(lu, ru->lch);
fix(ru);
return ru;
}
}
pair<node_y*, node_y*> split(node_y *u, pair<int, int> pos) {
if (!u) {
return {nullptr, nullptr};
}
if (u->pos <= pos) {
auto parts = split(u->rch, pos);
u->rch = parts.first;
fix(u);
return {u, parts.second};
}
else {
auto parts = split(u->lch, pos);
u->lch = parts.second;
fix(u);
return {parts.first, u};
}
}
void update_y(node_y *&root_y, int x, int y, long long val) {
node_y *part1, *part2, *part3;
tie(part1, part2) = split(root_y, {y, x - 1});
tie(part2, part3) = split(part2, {y, x});
root_y = merge(merge(part1, new node_y({y, x}, val)), part3);
}
long long get_y(node_y *&root_y, int ly, int ry) {
node_y *part1, *part2, *part3;
tie(part1, part2) = split(root_y, {ly, -1});
tie(part2, part3) = split(part2, {ry + 1, -1});
long long res = (part2 ? part2->g : 0);
root_y = merge(merge(part1, part2), part3);
return res;
}
struct node_x {
node_y *root_y;
node_x *lch;
node_x *rch;
node_x(): root_y(nullptr), lch(nullptr), rch(nullptr) {};
};
void update_x(node_x *&u, int lt, int rt, int x, int y, long long val) {
if (!u) {
u = new node_x();
}
update_y(u->root_y, x, y, val);
if (lt == rt) {
return;
}
int mt = (lt + rt) >> 1;
if (x <= mt) {
update_x(u->lch, lt, mt, x, y, val);
}
else {
update_x(u->rch, mt + 1, rt, x, y, val);
}
};
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++;
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);
}
