#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct node_y {
int lt = 0;
int rt = 0;
long long val = 0;
node_y *left = nullptr;
node_y *right = nullptr;
void init(int _lt, int _rt) {
lt = _lt;
rt = _rt;
}
};
int R, C;
struct node_x {
int lt = 0;
int rt = 0;
node_y *root_y = nullptr;
node_x *left = nullptr;
node_x *right = nullptr;
void init(int _lt, int _rt) {
lt = _lt;
rt = _rt;
root_y = new node_y();
root_y->init(0, (1 << 30) - 1);
}
};
node_x *root_x = new node_x();
void init(int _R, int _C) {
R = _R;
C = _C;
root_x->init(0, R - 1);
}
long long get_y(node_y *cur, int ly, int ry) {
if (!cur) {
return 0LL;
}
if (cur->rt < ly || cur->lt > ry) {
return 0LL;
}
if (ly <= cur->lt && cur->rt <= ry) {
return cur->val;
}
return __gcd(get_y(cur->left, ly, ry), get_y(cur->right, ly, ry));
}
void update_y(node_x *par, node_y *cur, int y, long long val) {
if (cur->lt == cur->rt) {
if (par->lt == par->rt) {
cur->val = val;
}
else {
cur->val = __gcd(par->left ? get_y(par->left->root_y, y, y) : 0LL, par->right ? get_y(par->right->root_y, y, y) : 0LL);
}
return;
}
int mt = (cur->lt + cur->rt) / 2;
if (y <= mt) {
if (!cur->left) {
cur->left = new node_y();
cur->left->init(cur->lt, mt);
}
int lt = cur->left->lt;
int rt = cur->left->rt;
int prv = -1;
while (y < lt || y > rt) {
int len = (rt - lt + 1);
if (lt & rt & len) {
prv = 1;
lt -= len;
}
else {
prv = 0;
rt += len;
}
}
if (prv == 0) {
node_y *mid = new node_y();
mid->init(lt, rt);
mid->left = cur->left;
cur->left = mid;
}
if (prv == 1) {
node_y *mid = new node_y();
mid->init(lt, rt);
mid->right = cur->left;
cur->left = mid;
}
update_y(par, cur->left, y, val);
}
else {
if (!cur->right) {
cur->right = new node_y();
cur->right->init(mt + 1, cur->rt);
}
int lt = cur->right->lt;
int rt = cur->right->rt;
int prv = -1;
while (y < lt || y > rt) {
int len = (rt - lt + 1);
if (lt & rt & len) {
prv = 1;
lt -= len;
}
else {
prv = 0;
rt += len;
}
}
if (prv == 0) {
node_y *mid = new node_y();
mid->init(lt, rt);
mid->left = cur->right;
cur->right = mid;
}
if (prv == 1) {
node_y *mid = new node_y();
mid->init(lt, rt);
mid->right = cur->right;
cur->right = mid;
}
update_y(par, cur->right, y, val);
}
cur->val = __gcd(cur->left ? cur->left->val : 0LL, cur->right ? cur->right->val : 0LL);
}
void update_x(node_x *cur, int x, int y, long long val) {
if (cur->lt == cur->rt) {
update_y(cur, cur->root_y, y, val);
return;
}
int mt = (cur->lt + cur->rt) / 2;
if (x <= mt) {
if (!cur->left) {
cur->left = new node_x();
cur->left->init(cur->lt, mt);
}
update_x(cur->left, x, y, val);
}
else {
if (!cur->right) {
cur->right = new node_x();
cur->right->init(mt + 1, cur->rt);
}
update_x(cur->right, x, y, val);
}
update_y(cur, cur->root_y, y, val);
}
void update(int x, int y, long long val) {
update_x(root_x, x, y, val);
}
long long get_x(node_x *cur, int lx, int rx, int ly, int ry) {
if (!cur) {
return 0LL;
}
if (cur->rt < lx || cur->lt > rx) {
return 0LL;
}
if (lx <= cur->lt && cur->rt <= rx) {
return get_y(cur->root_y, ly, ry);
}
return __gcd(get_x(cur->left, lx, rx, ly, ry), get_x(cur->right, lx, rx, ly, ry));
}
long long calculate(int lx, int ly, int rx, int ry) {
return get_x(root_x, lx, rx, ly, ry);
}
