#include "game.h"
#define ll long long
const int NODE_Y_MAX = 8e6;
const int NODE_X_MAX = 4e6;
const int NMAX = 1e9;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int n, m, root_x;
int nodes_y, nodes_x;
struct NodeY {
ll gcd;
int left, right;
NodeY() : gcd(0), left(0), right(0) {}
}aint_y[NODE_Y_MAX + 1];
struct NodeX {
int root_y;
int left, right;
NodeX() : root_y(0), left(0), right(0) {}
}aint_x[NODE_X_MAX + 1];
int create_node_x() {
nodes_x++;
return nodes_x;
}
int create_node_y() {
nodes_y++;
return nodes_y;
}
void updateY(int& node, int left, int right, int pos, ll value) {
if(!node) {
node = create_node_y();
}
if(left == right) {
aint_y[node].gcd = value;
return;
}
int mid = (left + right) / 2;
if(pos <= mid) {
updateY(aint_y[node].left, left, mid, pos, value);
}
else {
updateY(aint_y[node].right, mid + 1, right, pos, value);
}
aint_y[node].gcd = gcd2(aint_y[aint_y[node].left].gcd, aint_y[aint_y[node].right].gcd);
}
ll queryY(int node, int left, int right, int qleft, int qright) {
if(!node || left > qright || right < qleft) {
return 0;
}
if(left >= qleft && right <= qright) {
return aint_y[node].gcd;
}
int mid = (left + right) / 2;
return gcd2(queryY(aint_y[node].left, left, mid, qleft, qright), queryY(aint_y[node].right, mid + 1, right, qleft, qright));
}
void updateX(int& node, int left_x, int right_x, int pos_x, int pos_y, ll value) {
if(!node) {
node = create_node_x();
}
if(left_x == right_x) {
updateY(aint_x[node].root_y, 1, m, pos_y, value);
return;
}
int mid_x = (left_x + right_x) / 2;
if(pos_x <= mid_x) {
updateX(aint_x[node].left, left_x, mid_x, pos_x, pos_y, value);
}
else {
updateX(aint_x[node].right, mid_x + 1, right_x, pos_x, pos_y, value);
}
ll new_gcd = gcd2(queryY(aint_x[aint_x[node].left].root_y, 1, m, pos_y, pos_y), queryY(aint_x[aint_x[node].right].root_y, 1, m, pos_y, pos_y));
updateY(aint_x[node].root_y, 1, m, pos_y, new_gcd);
}
ll queryX(int node, int left_x, int right_x, int qleft_x, int qleft_y, int qright_x, int qright_y) {
if(!node || left_x > qright_x || right_x < qleft_x) {
return 0;
}
if(left_x >= qleft_x && right_x <= qright_x) {
return queryY(aint_x[node].root_y, 1, m, qleft_y, qright_y);
}
int mid_x = (left_x + right_x) / 2;
return gcd2(queryX(aint_x[node].left, left_x, mid_x, qleft_x, qleft_y, qright_x, qright_y), queryX(aint_x[node].right, mid_x + 1, right_x, qleft_x, qleft_y, qright_x, qright_y));
}
void init(int R, int C) {
n = R; m = C;
root_x = create_node_x();
}
void update(int P, int Q, long long K) {
P++; Q++;
updateX(root_x, 1, n, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
P++; Q++; U++; V++;
return queryX(root_x, 1, n, P, Q, U, V);
}
