#include "game.h"
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
typedef long long ll;
using namespace std;
long long gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X, X = Y, Y = tmp % Y;
}
return X;
}
const int K = 50;
int r, c, last = 0;
vector<vector<ll> > st;
vector<vector<int> > val;
vector<int> x;
struct upd { int x, y; ll k; };
void init(int R, int C) { r = R, c = C; }
ll query_1d(int li, int ri, int vr) {
ll g = 0;
li = lower_bound(val[vr].begin(), val[vr].end(), li) - val[vr].begin();
ri = upper_bound(val[vr].begin(), val[vr].end(), ri) - val[vr].begin();
for (li += val[vr].size(), ri += val[vr].size(); li < ri; li >>= 1, ri >>= 1) {
if (li & 1) g = gcd(g, st[vr][li++]);
if (ri & 1) g = gcd(g, st[vr][--ri]);
} return g;
}
vector<upd> u;
map<pair<int, int>, ll> m;
ll query_2d(int lx, int ly, int rx, int ry) {
lx = lower_bound(x.begin(), x.end(), lx) - x.begin();
rx = upper_bound(x.begin(), x.end(), rx) - x.begin();
ll g = 0;
for (lx += x.size(), rx += x.size(); lx < rx; lx >>= 1, rx >>= 1) {
if (lx & 1) g = gcd(g, query_1d(ly, ry, lx++));
if (rx & 1) g = gcd(g, query_1d(ly, ry, --rx));
}
return g;
}
long long calculate(int lx, int ly, int rx, int ry) {
ll g = query_2d(lx, ly, rx, ry);
for (int i = last; i < u.size(); i++)
if (lx <= u[i].x && u[i].x <= rx && ly <= u[i].y && u[i].y <= ry)
g = gcd(g, u[i].k);
return g;
}
void merge(int v)
{
vector<ll> lf;
int lv = (v << 1), rv = ((v << 1) | 1), li = 0, ri = 0;
while (li < val[lv].size() || ri < val[rv].size()) {
int i, j;
if (ri == val[rv].size() || (li < val[lv].size() && val[lv][li] < val[rv][ri])) i = lv, j = li++;
else i = rv, j = ri++;
if (val[v].empty() || val[v].back() < val[i][j]) val[v].push_back(val[i][j]), lf.push_back(0);
lf.back() = gcd(lf.back(), st[i][val[i].size() + j]);
}
st[v].assign(lf.size() * 2, 0);
for (int i = 0; i < lf.size(); i++) st[v][i + lf.size()] = lf[i];
}
void update(int X, int Y, ll k) {
u.push_back({ X, Y, k });
if (m.count({ X, Y })) u[m[{X, Y}]].x = -1;
m[{X, Y}] = u.size() - 1;
if (last + K > u.size()) return;
x.clear();
for (int i = 0; i < u.size(); i++) if (u[i].x > -1) x.push_back(u[i].x);
sort(x.begin(), x.end()), x.erase(unique(x.begin(), x.end()), x.end());
int n = x.size();
val.assign(2 * n, vector<int>()), st.assign(n * 2, vector<ll>());
for (int i =0; i < u.size(); i++) {
if (u[i].x == -1) continue;
int ix = lower_bound(x.begin(), x.end(), u[i].x) - x.begin();
val[n + ix].push_back(u[i].y);
}
for (int i = n; i < 2 * n; i++) {
sort(val[i].begin(), val[i].end());
val[i].erase(unique(val[i].begin(), val[i].end()), val[i].end());
st[i].assign(val[i].size() * 2, 0);
}
for (const upd& i : u) {
if (i.x == -1) continue;
int ix = lower_bound(x.begin(), x.end(), i.x) - x.begin();
int iy = lower_bound(val[n + ix].begin(), val[n + ix].end(), i.y) - val[n + ix].begin();
st[n + ix][val[n + ix].size() + iy] = i.k;
}
for (int i = n - 1; i > 0; i--)
merge(i);
for (int i = 0; i < 2 * n; i++)
for (int j = val[i].size() - 1; j > 0; j--) st[i][j] = gcd(st[i][j << 1], st[i][(j << 1) | 1]);
last = u.size();
}
