#include "game.h"
#include <algorithm>
using namespace std;
struct NODE {
long long num;
NODE *left, *right;
};
struct TREE {
TREE *left, *right;
NODE *node_top;
} *top;
int n, n_d, m, m_d;
long long gcd(long long x, long long y) {
long long tmp;
while (x != y && y != 0) {
tmp = x, x = y, y = tmp % y;
} return x;
}
NODE* make_NODE() {
NODE *temp = (NODE*)malloc(sizeof(NODE));
temp->num = 0, temp->left = temp->right = NULL;
return temp;
}
TREE* make_TREE() {
TREE *temp = (TREE*)malloc(sizeof(TREE));
temp->node_top = make_NODE();
temp->left = temp->right = NULL;
return temp;
}
void init(int _n, int _m) {
n = _n, m = _m;
for (n_d = 1; n_d < n; n_d *= 2);
for (m_d = 1; m_d < m; m_d *= 2);
top = make_TREE();
}
long long get_NODE(NODE *node, int l, int r, int x, int y) {
int mid = (l + r) / 2;
long long res_l = 0, res_r = 0;
if (r < x || y < l) return 0;
//printf(" ==== %d %d %d %d / %d %d\n", l, r, x, y, node->left != NULL, node->right != NULL);
if (x <= l && r <= y) return node->num;
if (node->left != NULL) res_l = get_NODE(node->left, l, mid, x, y);
if (node->right != NULL) res_r = get_NODE(node->right, mid + 1, r, x, y);
return gcd(res_l, res_r);
}
long long get_TREE(TREE *tree, int l, int r, int x, int y, int p_x, int p_y) {
int mid = (l + r) / 2;
long long res_l = 0, res_r = 0;
if (r < x || y < l) return 0;
if (x <= l && r <= y) {return get_NODE(tree->node_top, 1, m_d, p_x, p_y);
}
if (tree->left != NULL) res_l = get_TREE(tree->left, l, mid, x, y, p_x, p_y);
if (tree->right != NULL) res_r = get_TREE(tree->right, mid + 1, r, x, y, p_x, p_y);
return gcd(res_l, res_r);
}
long long calculate(int y_l, int x_l, int y_r, int x_r) {
// printf(" >>> %lld\n", top->node_top->left->num);
return get_TREE(top, 1, n_d, y_l + 1, y_r + 1, x_l + 1, x_r + 1);
}
void Push_NODE(NODE *node, int l, int r, int w, long long num) {
int mid = (l + r) / 2;
if (r < w || w < l) return;
if (l == w && r == w) {
node->num = num;
return;
}
if (node->left == NULL) node->left = make_NODE();
if (node->right == NULL) node->right = make_NODE();
Push_NODE(node->left, l, mid, w, num);
Push_NODE(node->right, mid + 1, r, w, num);
node->num = gcd(node->left->num, node->right->num);
}
long long Push_TREE(TREE *tree, int l, int r, int w, int p_x, long long p_num) {
int mid = (l + r) / 2;
if (r < w || w < l) return get_NODE(tree->node_top, 1, m_d, p_x, p_x);
if (l == w && r == w) {
// printf("(%d %d) - %d = %lld\n", l, r, p_x, p_num);
Push_NODE(tree->node_top, 1, m_d, p_x, p_num);
return p_num;
}
if (tree->left == NULL) tree->left = make_TREE();
if (tree->right == NULL) tree->right = make_TREE();
long long a = Push_TREE(tree->left, l, mid, w, p_x, p_num);
long long b = Push_TREE(tree->right, mid + 1, r, w, p_x, p_num);
long long Push_num = gcd(a, b);
Push_NODE(tree->node_top, 1, m_d, p_x, Push_num);
// printf("(%d %d) - %d = %lld\n", l, r, p_x, Push_num);
return Push_num;
}
void update(int y, int x, long long num) {
Push_TREE(top, 1, n_d, y + 1, x + 1, num);
}
