#include "game.h"
#include <bits/stdc++.h>
using namespace std;
int r, c;
long long gcd(long long a, long long b) {
while (b > 0) {
swap(a, b);
b %= a;
}
return a;
}
struct node {
int l, r, idx;
long long val;
node *left, *right;
node(int _l, int _r) : l(_l), r(_r), idx(-1), val(-1), left(nullptr), right(nullptr) {}
};
void update(node *cur, int idx, long long val);
void propagate(node *cur, int idx, long long val) {
if (idx <= (cur->l + cur->r) / 2) {
if (cur->left == nullptr) cur->left = new node(cur->l, (cur->l + cur->r) / 2);
update(cur->left, idx, val);
} else {
if (cur->right == nullptr) cur->right = new node((cur->l + cur->r) / 2 + 1, cur->r);
update(cur->right, idx, val);
}
}
void update(node *cur, int idx, long long val) {
if (cur->l == cur->r) {
cur->val = val;
return;
}
if (cur->idx == idx) cur->val = val;
else if (cur->idx != -1) {
propagate(cur, cur->idx, cur->val);
cur->idx = -1;
} else if (cur->val == -1) {
cur->idx = idx, cur->val = val;
return;
}
propagate(cur, idx, val);
cur->val = gcd(cur->left == nullptr ? 0 : cur->left->val, cur->right == nullptr ? 0 : cur->right->val);
}
long long query(node *cur, int l, int r) {
if (l <= cur->l && cur->r <= r) return cur->val;
if (l > cur->r || r < cur->l) return 0;
if (cur->idx != -1) return (l <= cur->idx && cur->idx <= r) ? cur->val : 0;
long long ans = 0;
if (cur->left != nullptr) ans = gcd(ans, query(cur->left, l, r));
if (cur->right != nullptr) ans = gcd(ans, query(cur->right, l, r));
return ans;
}
struct node2D {
int l, r;
node *root;
node2D *left, *right;
node2D(int _l, int _r) : l(_l), r(_r), root(nullptr), left(nullptr), right(nullptr) {}
} *root;
void update2D(node2D *cur, int x, int y, long long val) {
if (cur->root == nullptr) cur->root = new node(0, c - 1);
if (cur->l == cur->r) {
update(cur->root, y, val);
return;
}
if (x <= (cur->l + cur->r) / 2) {
if (cur->left == nullptr) cur->left = new node2D(cur->l, (cur->l + cur->r) / 2);
update2D(cur->left, x, y, val);
} else {
if (cur->right == nullptr) cur->right = new node2D((cur->l + cur->r) / 2 + 1, cur->r);
update2D(cur->right, x, y, val);
}
update(cur->root, y, gcd(cur->left == nullptr ? 0 : query(cur->left->root, y, y), cur->right == nullptr ? 0 : query(cur->right->root, y, y)));
}
long long query2D(node2D *cur, int x1, int y1, int x2, int y2) {
if (cur->l > x2 || cur->r < x1) return 0;
if (x1 <= cur->l && cur->r <= x2) return cur->root == nullptr ? 0 : query(cur->root, y1, y2);
long long ans = 0;
if (cur->left != nullptr) ans = gcd(ans, query2D(cur->left, x1, y1, x2, y2));
if (cur->right != nullptr) ans = gcd(ans, query2D(cur->right, x1, y1, x2, y2));
return ans;
}
void init(int R, int C) {
r = R, c = C;
root = new node2D(0, r - 1);
}
void update(int P, int Q, long long K) {
update2D(root, P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
return query2D(root, P, Q, U, V);
}
