#include <bits/stdc++.h>
using namespace std;
typedef long long nagai;
#include "game.h"
//pizda
template<typename T>
class fake_ptr {
private:
uint32_t null = -1;
public:
static vector<T>& mem() {
static vector<T> mem_;
return mem_;
}
static void reserve(int cnt) {
mem().reserve(cnt);
}
static fake_ptr make() {
mem().push_back({});
return fake_ptr{static_cast<uint32_t>(mem().size() - 1)};
}
fake_ptr() : arr_ind{null} {}
explicit fake_ptr(uint32_t arr_ind) : arr_ind{arr_ind} {};
T* operator ->() {
assert(arr_ind != null);
return &mem()[arr_ind];
}
fake_ptr& operator=(const fake_ptr& o) {
arr_ind = o.arr_ind;
return *this;
}
operator bool() {
return arr_ind != null;
}
std::uint32_t arr_ind;
};
//template<typename T>
//vector<T> fake_ptr<T>::mem = {};
template<typename T>
fake_ptr<T> make_fake() {
return fake_ptr<T>::make();
}
nagai gcd(nagai a, nagai b)
{
while (b)
a = a % b, swap(a, b);
return a;
}
template<int H>
struct sl
{
struct nd
{
vector<fake_ptr<nd>> ri;
vector<nagai> gcd;
// vector<int> len;
pair<int, int> x;
inline int sz()
{
return ri.size();
}
};
fake_ptr<nd> header;
sl() {
header = make_fake<nd>();
header->ri.resize(H, {});
header->gcd.resize(H, 0);
header->x = {-1, -1};
//header->len.resize(H, 0);
}
fake_ptr<nd> last[H];
int len[H];
void go(pair<int, int> to)
{
fake_ptr<nd> cur = header;
for (int i = H - 1; i >= 0; --i)
{
while (i < cur->ri.size() && cur->ri[i] && cur->ri[i]->x < to)
cur = cur->ri[i];
last[i] = cur;
}
}
inline nagai calc(fake_ptr<nd> a, fake_ptr<nd> b, int i)
{
nagai g = a->gcd[i];
while (!b && a->ri[i] || b && a->ri[i] && a->ri[i]->x < b->x)
a = a->ri[i], g = gcd(g, a->gcd[i]);
//cerr << a->x << ' ' << (b ? b->x : -2) << ' ' << i << ' ' << g << endl;
return g;
}
void insert(pair<int, int> ind, nagai val)
{
go(ind);
fake_ptr<nd> nw = make_fake<nd>();
nw->x = ind;
for (int i = 0, add = 1; i < H; add &= rand(), ++i)
{
if (add)
{
if (i > 0)
{
nagai g = calc(last[i], nw, i - 1);
nagai g1 = calc(nw, last[i]->ri[i], i - 1);
//cerr << "kek " << g << ' ' << last[i]->x << ' ' << last[i]->gcd[i - 1] << endl;
last[i]->gcd[i] = g;
nw->gcd.push_back(g1);
}
else
nw->gcd.push_back(val);
nw->ri.push_back(last[i]->ri[i]);
last[i]->ri[i] = nw;
}
else
{
last[i]->gcd[i] = gcd(last[i]->gcd[i], val);
}
}
}
void erase(pair<int, int> ind)
{
go(ind);
for (int i = 0; i < H; ++i)
{
if (last[i]->ri[i] && last[i]->ri[i]->x == ind)
{
if (i)
last[i]->gcd[i] = calc(last[i], last[i]->ri[i]->ri[i], i - 1);
last[i]->ri[i] = last[i]->ri[i]->ri[i];
}
else
last[i]->gcd[i] = calc(last[i], last[i]->ri[i], i - 1);
}
}
void print()
{
for (int i = 0; i < H; ++i)
{
auto v = header;
while (v)
cerr << '{' << v->x.first << ',' << v->x.second << '}' << ',' << v->gcd[i] << ' ', v = v->ri[i];
cerr << endl;
}
}
nagai get(pair<int, int> l, pair<int, int> r)
{
nagai g = 0;
go(l);
fake_ptr<nd> kek = last[0]->ri[0];
if (!kek)
return 0;
//cerr << kek->x.first << ' ' << kek->x.second << endl;
for (int i = 0; i < H; ++i)
while (i < kek->sz() && i + 1 >= kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
//cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
for (int i = H - 1; i >= 0; --i)
while (i < kek->sz() && kek->ri[i] && kek->ri[i]->x < r)
g = gcd(g, kek->gcd[i]), kek = kek->ri[i];
//cerr << kek->x.first << ' ' << kek->x.second << ' ' << g << endl;
if (kek->x < r)
g = gcd(g, kek->gcd[0]);
return g;
}
};
struct nd
{
nd* le;
nd* ri;
sl<18> skip;
nd()
: le(nullptr), ri(nullptr)
{}
void children()
{
if (!le)
le = new nd();
if (!ri)
ri = new nd();
}
void add(int l, int r, int x, int y, nagai val, bool add)
{
if (l > x || r <= x)
return;
if (add)
skip.insert({y, x}, val);
else
skip.erase({y, x});
if (r - l == 1)
return;
children();
int m = (l + r) / 2;
le->add(l, m, x, y, val, add);
ri->add(m, r, x, y, val, add);
}
nagai get(int l, int r, int ql1, int qr1, int ql2, int qr2)
{
//skip.print();
if (l >= qr1 || ql1 >= r)
return 0;
if (ql1 <= l && r <= qr1)
return skip.get({ql2, ql1}, {qr2, ql1});
if (!le && !ri)
return 0;
int m = (l + r) / 2;
if (!le)
return ri->get(m, r, ql1, qr1, ql2, qr2);
if (!ri)
return le->get(l, m, ql1, qr1, ql2, qr2);
return gcd(le->get(l, m, ql1, qr1, ql2, qr2),
ri->get(m, r, ql1, qr1, ql2, qr2));
}
};
nd* rt = new nd;
int MX = 1000000010;
set<pair<int, int>> p;
void init(int R, int C)
{
MX = R;
}
void update(int x, int y, long long t)
{
if (p.count({x, y}))
rt->add(0, MX, x, y, t, 0);
rt->add(0, MX, x, y, t, 1);
p.insert({x, y});
}
long long calculate(int xl, int yl, int xr, int yr)
{
return rt->get(0, MX, xl, xr + 1, yl, yr + 1);
}
