#pragma GCC optimize ("O3")
#include "game.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vvi vector<vi>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define f first
#define s second
#define oo 1000000001
#define eb emplace_back
#define pb push_back
#define mpr make_pair
#define size(v) (int)v.size()
#define ln '\n'
#define ull unsigned long long
#define ll long long
#define all(v) v.begin(), v.end()
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXR = 1e9;
const int MAXC = 1e9;
struct tree1D {
tree1D *left, *right;
ll GCD;
tree1D(): left(nullptr), right(nullptr), GCD(0) {}
void update1D(tree1D *tr, int l, int r, int pos, ll val) {
if (l == r) {
tr->GCD = val;
} else {
int mid = (l + r) >> 1;
if (pos <= mid) {
if (tr->left == nullptr) tr->left = new tree1D();
update1D(tr->left, l, mid, pos, val);
} else {
if (tr->right == nullptr) tr->right = new tree1D();
update1D(tr->right, mid + 1, r, pos, val);
}
if (tr->left == nullptr) tr->GCD = tr->right->GCD;
else if (tr->right == nullptr) tr->GCD = tr->left->GCD;
else tr->GCD = __gcd(tr->left->GCD, tr->right->GCD);
}
}
ll query1D(tree1D *tr, int l, int r, int ql, int qr) {
if (ql > r || l > qr) return 0;
else if (ql <= l && r <= qr) return tr->GCD;
else {
int mid = (l + r) >> 1;
ll q1 = 0, q2 = 0;
if (tr->left != nullptr) q1 = query1D(tr->left, l, mid, ql, qr);
if (tr->right != nullptr) q2 = query1D(tr->right, mid + 1, r, ql, qr);
return __gcd(q1, q2);
}
}
};
struct tree2D {
tree2D *left, *right;
tree1D *tree_1D;
tree2D(): left(nullptr), right(nullptr), tree_1D(new tree1D()) {}
void update2D(tree2D *tr, int l, int r, int pos_r, int pos_c, ll val) {
tr->tree_1D->update1D(tr->tree_1D, 1, MAXC, pos_c, val);
if (l < r) {
int mid = (l + r) >> 1;
if (pos_r <= mid) {
if (tr->left == nullptr) tr->left = new tree2D();
update2D(tr->left, l, mid, pos_r, pos_c, val);
} else {
if (tr->right == nullptr) tr->right = new tree2D();
update2D(tr->right, mid + 1, r, pos_r, pos_c, val);
}
}
}
ll query2D(tree2D *tr, int l, int r, int row_l, int row_r, int col_l, int col_r) {
if (row_l > r || l > row_r) return 0;
else if (row_l <= l && r <= row_r) return tr->tree_1D->query1D(tr->tree_1D, 1, MAXC, col_l, col_r);
else {
int mid = (l + r) >> 1;
ll q1 = 0, q2 = 0;
if (tr->left != nullptr) q1 = query2D(tr->left, l, mid, row_l, row_r, col_l, col_r);
if (tr->right != nullptr) q2 = query2D(tr->right, mid + 1, r, row_l, row_r, col_l, col_r);
return __gcd(q1, q2);
}
}
};
/// usage
/// tree2D *tr = new tree2D()
/// tr->update2D(tr, 1, MAXR, row, col, val)
/// tr->query2D(tr, 1, MAXR, row_l, row_r, col_l, col_r)
tree2D *tr;
void init(int R, int C) {
tr = new tree2D();
}
void update(int P, int Q, ll K) {
++P;
++Q;
tr->update2D(tr, 1, MAXR, P, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
++P;
++Q;
++U;
++V;
return tr->query2D(tr, 1, MAXR, P, U, Q, V);
}
