#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
typedef unordered_map <int, ll> umap;
const int offset = 1 << 30;
const int MAX_ROW = 6.7e5;
int row_root;
int l[MAX_ROW], r[MAX_ROW];
umap num[MAX_ROW];
ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}
void create_row(int &node) {
static int sz;
if (!node)
node = ++sz;
}
void init(int R, int C) {
create_row(row_root);
}
ll get(umap &ref, ll val) {
return ref.find(val) == ref.end() ? 0 : ref[val];
}
void update_col(umap &tour, umap &lft, umap &rig, int x, ll val) {
x += offset;
tour[x] = gcd(get(lft, x), get(rig, x));
if (!tour[x])
tour[x] = val;
for (x /= 2; x; x /= 2)
tour[x] = gcd(get(tour, 2 * x), get(tour, 2 * x + 1));
}
void update_row(int x, int lo, int hi, int row, int col, ll val) {
if (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (row < mid) {
create_row(l[x]);
update_row(l[x], lo, mid, row, col, val);
}
else {
create_row(r[x]);
update_row(r[x], mid, hi, row, col, val);
}
}
update_col(num[x], num[l[x]], num[r[x]], col, val);
}
void update(int p, int q, ll k) {
update_row(row_root, 0, offset, p, q, k);
}
ll query_col(umap &tour, int x, int lo, int hi, int from, int to) {
if (lo >= to || hi <= from || tour.find(x) == tour.end())
return 0;
if (lo >= from && hi <= to)
return tour[x];
int mid = (lo + hi) / 2;
return gcd(query_col(tour, 2 * x, lo, mid, from, to), query_col(tour, 2 * x + 1, mid, hi, from, to));
}
ll query_row(int 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(num[x], 1, 0, offset, col1, col2);
int mid = (lo + hi) / 2;
return gcd(query_row(l[x], lo, mid, from, to, col1, col2), query_row(r[x], 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);
}
