#include "game.h"
#include <bits/stdc++.h>
using namespace std;
struct node_y {
int lt = 0;
int rt = 0;
long long val = 0;
int left = 0;
int right = 0;
void init(int _lt, int _rt) {
lt = _lt;
rt = _rt;
}
};
const int max_nodes = 2e6 + 20;
int node_x_cnt = 0;
int node_y_cnt = 0;
int R, C;
node_y nodes_y[max_nodes];
struct node_x {
int lt = 0;
int rt = 0;
int root_y = 0;
int left = 0;
int right = 0;
void init(int _lt, int _rt) {
lt = _lt;
rt = _rt;
root_y = ++node_y_cnt;
nodes_y[root_y].init(0, (1 << 30) - 1);
}
};
node_x nodes_x[max_nodes];
int root_x = ++node_x_cnt;
void init(int _R, int _C) {
R = _R;
C = _C;
nodes_x[root_x].init(0, R - 1);
}
long long get_y(int cur, int ly, int ry) {
if (!cur) {
return 0LL;
}
if (nodes_y[cur].rt < ly || nodes_y[cur].lt > ry) {
return 0LL;
}
if (ly <= nodes_y[cur].lt && nodes_y[cur].rt <= ry) {
return nodes_y[cur].val;
}
return __gcd(get_y(nodes_y[cur].left, ly, ry), get_y(nodes_y[cur].right, ly, ry));
}
void update_y(int par, int cur, int y, long long val) {
if (nodes_y[cur].lt == nodes_y[cur].rt) {
if (nodes_x[par].lt == nodes_x[par].rt) {
nodes_y[cur].val = val;
}
else {
nodes_y[cur].val = __gcd(nodes_x[par].left ? get_y(nodes_x[nodes_x[par].left].root_y, y, y) : 0LL, nodes_x[par].right ? get_y(nodes_x[nodes_x[par].right].root_y, y, y) : 0LL);
}
return;
}
int mt = (nodes_y[cur].lt + nodes_y[cur].rt) / 2;
if (y <= mt) {
if (!nodes_y[cur].left) {
nodes_y[cur].left = ++node_y_cnt;
nodes_y[nodes_y[cur].left].init(y, y);
}
int lt = nodes_y[nodes_y[cur].left].lt;
int rt = nodes_y[nodes_y[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) {
int mid = ++node_y_cnt;
nodes_y[mid].init(lt, rt);
nodes_y[mid].left = nodes_y[cur].left;
nodes_y[cur].left = mid;
}
if (prv == 1) {
int mid = ++node_y_cnt;
nodes_y[mid].init(lt, rt);
nodes_y[mid].right = nodes_y[cur].left;
nodes_y[cur].left = mid;
}
update_y(par, nodes_y[cur].left, y, val);
}
else {
if (!nodes_y[cur].right) {
nodes_y[cur].right = ++node_y_cnt;
nodes_y[nodes_y[cur].right].init(y, y);
}
int lt = nodes_y[nodes_y[cur].right].lt;
int rt = nodes_y[nodes_y[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) {
int mid = ++node_y_cnt;
nodes_y[mid].init(lt, rt);
nodes_y[mid].left = nodes_y[cur].right;
nodes_y[cur].right = mid;
}
if (prv == 1) {
int mid = ++node_y_cnt;
nodes_y[mid].init(lt, rt);
nodes_y[mid].right = nodes_y[cur].right;
nodes_y[cur].right = mid;
}
update_y(par, nodes_y[cur].right, y, val);
}
nodes_y[cur].val = __gcd(nodes_y[cur].left ? nodes_y[nodes_y[cur].left].val : 0LL, nodes_y[cur].right ? nodes_y[nodes_y[cur].right].val : 0LL);
}
void update_x(int cur, int x, int y, long long val) {
if (nodes_x[cur].lt == nodes_x[cur].rt) {
update_y(cur, nodes_x[cur].root_y, y, val);
return;
}
int mt = (nodes_x[cur].lt + nodes_x[cur].rt) / 2;
if (x <= mt) {
if (!nodes_x[cur].left) {
nodes_x[cur].left = ++node_x_cnt;
nodes_x[nodes_x[cur].left].init(nodes_x[cur].lt, mt);
}
update_x(nodes_x[cur].left, x, y, val);
}
else {
if (!nodes_x[cur].right) {
nodes_x[cur].right = ++node_x_cnt;
nodes_x[nodes_x[cur].right].init(mt + 1, nodes_x[cur].rt);
}
update_x(nodes_x[cur].right, x, y, val);
}
update_y(cur, nodes_x[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(int cur, int lx, int rx, int ly, int ry) {
if (!cur) {
return 0LL;
}
if (nodes_x[cur].rt < lx || nodes_x[cur].lt > rx) {
return 0LL;
}
if (lx <= nodes_x[cur].lt && nodes_x[cur].rt <= rx) {
return get_y(nodes_x[cur].root_y, ly, ry);
}
return __gcd(get_x(nodes_x[cur].left, lx, rx, ly, ry), get_x(nodes_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);
}
