#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
const int offset = 1 << 30;
struct ColumnNode {
ll num;
ColumnNode *l, *r;
ColumnNode() : num(0), l(nullptr), r(nullptr) {}
};
struct RowNode {
ColumnNode* root;
RowNode *l, *r;
RowNode() : root(new ColumnNode()), l(nullptr), r(nullptr) {}
};
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
RowNode* row_root;
void init(int R, int C) {
row_root = new RowNode();
}
void update_col(ColumnNode *x, int lo, int hi, int col, ll val) {
if (col < lo || col >= hi)
return;
if (hi - lo == 1) {
x -> num = val;
return;
}
int mid = (lo + hi) / 2;
if (!(x -> l))
x -> l = new ColumnNode();
if (!(x -> r))
x -> r = new ColumnNode();
update_col(x -> l, lo, mid, col, val);
update_col(x -> r, mid, hi, col, val);
x -> num = gcd(x -> l -> num, x -> r -> num);
}
void update_row(RowNode* x, int lo, int hi, int row, int col, ll val) {
update_col(x -> root, 0, offset, col, val);
if (hi - lo == 1)
return;
int mid = (lo + hi) / 2;
if (row < mid) {
if (!(x -> l))
x -> l = new RowNode();
update_row(x -> l, lo, mid, row, col, val);
}
else {
if (!(x -> r))
x -> r = new RowNode();
update_row(x -> r, mid, hi, row, col, val);
}
}
void update(int p, int q, ll k) {
update_row(row_root, 0, offset, p, q, k);
}
ll query_col(ColumnNode* x, int lo, int hi, int from, int to) {
if (!x || lo >= to || hi <= from)
return 0;
if (lo >= from && hi <= to)
return x -> num;
int mid = (lo + hi) / 2;
return gcd(query_col(x -> l, lo, mid, from, to), query_col(x -> r, mid, hi, from, to));
}
ll query_row(RowNode* x, int lo, int hi, int from, int to, int col1, int col2) {
if (!x || lo >= to || hi <= from)
return 0;
if (lo >= from && hi <= to)
return query_col(x -> root, 0, offset, col1, col2);
int mid = (lo + hi) / 2;
return gcd(query_row(x -> l, lo, mid, from, to, col1, col2), query_row(x -> r, mid, hi, from, to, col1, col2));
}
ll calculate(int p, int q, int u, int v) {
return query_row(row_root, 0, offset, p, u + 1, q, v + 1);
}
