#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
using ll = long long;
constexpr int MAXQ = 22001;
#define left lft
#define right rght
//#define gcd my_gcd
ll my_gcd(ll a, ll b) {
if (!a || !b) return a ^ b;
ll c;
while ((c = a % b)) {
a = b;
b = c;
}
return b;
}
int R, C;
constexpr int M = MAXQ * 30 + 10;
int counter = 1;
ll d[M];
int left[M], right[M];
//vector<ll> d{{}};
//vector<int> left{{}}, right{{}};
int st_create() {
// d.emplace_back(), left.emplace_back(), right.emplace_back();
d[counter] = left[counter] = right[counter] = 0;
return counter++;
}
void st_update(int v, int i, ll k, int l, int r) {
int kek = 0;
static int pa[30];
while (l + 1 < r) {
int mid = (l + r) / 2;
pa[kek++] = v;
if (i < mid) {
if (!left[v]) {
left[v] = st_create();
}
v = left[v];
r = mid;
} else {
if (!right[v]) {
right[v] = st_create();
}
v = right[v];
l = mid;
}
}
d[v] = gcd(d[v], k);
for (int x = kek - 1; x >= 0; --x) {
v = pa[x];
d[v] = gcd(d[left[v]], d[right[v]]);
}
}
void set_update(int v, int i, ll k, int l, int r) {
int kek = 0;
static int pa[30];
while (l + 1 < r) {
int mid = (l + r) / 2;
pa[kek++] = v;
if (i < mid) {
if (!left[v]) {
left[v] = st_create();
}
v = left[v];
r = mid;
} else {
if (!right[v]) {
right[v] = st_create();
}
v = right[v];
l = mid;
}
}
d[v] = k;
for (int x = kek - 1; x >= 0; --x) {
v = pa[x];
d[v] = gcd(d[left[v]], d[right[v]]);
}
}
ll st_query(int v, int lx, int rx, int l, int r) {
if (lx >= r || rx <= l) {
return 0;
} else if (lx <= l && r <= rx) {
return d[v];
} else {
int mid = (l + r) / 2;
ll ans = 0;
if (left[v]) {
ans = gcd(ans, st_query(left[v], lx, rx, l, mid));
}
if (right[v]) {
ans = gcd(ans, st_query(right[v], lx, rx, mid, r));
}
return ans;
}
}
void clear(int v) {
if (!v) return;
d[v] = 0;
clear(left[v]);
clear(right[v]);
}
constexpr int B = 250;
map<pair<int, int>, ll> mp;
constexpr int maxK = MAXQ / B + 1;
pair<int, int> l[maxK], r[maxK];
map<int, multiset<ll>> mapp[maxK];
int root[maxK], top = 0;
void rebuild() {
counter = 1;
top = 0;
int last_sz = 0;
for (auto [xx, k]: mp) {
if (last_sz == B) {
last_sz = 0;
}
if (last_sz == 0) {
l[top] = xx;
r[top] = xx;
root[top++] = st_create();
} else {
r[top - 1] = xx;
}
last_sz += 1;
st_update(root[top - 1], xx.second, k, 0, C);
}
}
int last_rebuild = 0;
void insert(pair<int, int> xx, ll k) {
auto it = mp.find(xx);
bool was;
ll last = -1;
if (it != mp.end()) {
was = true;
last = it->second;
} else {
was = false;
}
mp[xx] = k;
++last_rebuild;
if (last_rebuild == B) {
last_rebuild = 0;
rebuild();
return;
}
int i = -1;
if (xx >= r[top - 1]) {
i = top - 1;
} else if (xx <= l[0]) {
i = 0;
} else {
for (int j = top - 1; j >= 0; --j) {
if (l[j] <= xx) {
i = j;
break;
}
}
}
assert(i != -1);
l[i] = min(l[i], xx);
r[i] = max(r[i], xx);
int y = xx.second;
auto &st = mapp[i][y];
if (was) {
st.extract(last);
}
st.insert(k);
if (was) {
ll dc = 0;
for (ll dd : st) {
dc = gcd(dc, dd);
}
set_update(root[i], xx.second, dc, 0, C);
} else {
st_update(root[i], xx.second, k, 0, C);
}
}
void init(int R, int C) {
::R = R, ::C = C;
l[0] = {R + 1, C + 1}, r[0] = {0, 0};
root[top++] = st_create();
}
void update(int P, int Q, ll K) {
insert({P, Q}, K);
}
ll calculate(int P, int Q, int U, int V) {
ll cd = 0;
pair<int, int> min_done = {U, V + 1};
pair<int, int> max_done = {P, Q - 1};
for (int i = 0; i < top; ++i) {
if (l[i].first >= P && r[i].first <= U) {
cd = gcd(cd, st_query(root[i], Q, V + 1, 0, C));
min_done = min(min_done, l[i]);
max_done = max(max_done, r[i]);
}
}
auto it = mp.upper_bound(max_done);
for (; it != mp.end() && it->first.first <= U; it = next(it)) {
if (it->first.second >= Q && it->first.second <= V) {
cd = gcd(cd, it->second);
}
}
if (min_done <= max_done) {
it = mp.lower_bound(min_done);
for (; it != mp.begin() && prev(it)->first.first >= P;) {
it = prev(it);
if (it->first.second >= Q && it->first.second <= V) {
cd = gcd(cd, it->second);
}
}
}
return cd;
}
