#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int BIGBUCK = 64;
const int LILBUCK = 8;
const int MAX_N = 22000;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int R, C;
struct Cell {
int r, c;
long long val;
bool operator< (const Cell &a) const {
return r < a.r || (r == a.r && c < a.c);
}
};
bool cmp(Cell a, Cell b) {
return a.c < b.c;
}
struct Bucket {
int x1, x2;
int sizebuck, nrb;
Cell cell[BIGBUCK];
int y1[BIGBUCK / LILBUCK + 1], y2[BIGBUCK / LILBUCK + 1];
long long buckRez[BIGBUCK / LILBUCK + 1];
void init() {
x1 = x2 = 0;
sizebuck = nrb = 0;
for(int i = 0; i < BIGBUCK; ++i)
cell[i] = {0, 0, 0};
for(int i = 0; i < BIGBUCK / LILBUCK + 1; ++i)
y1[i] = y2[i] = buckRez[i] = 0;
}
void pushCell(Cell x) {
cell[sizebuck++] = x;
}
void build() {
std::sort(cell, cell + sizebuck, cmp);
for(int i = 0; i < sizebuck; ++i) {
if(i % LILBUCK == 0) {
y1[nrb] = cell[i].c;
++nrb;
}
buckRez[nrb - 1] = gcd2(buckRez[nrb - 1], cell[i].val);
y2[nrb - 1] = cell[i].c;
}
}
long long stankyleg(int yl, int yr) {
long long rez = 0LL;
for(int i = 0; i < nrb; ++i)
if(yl <= y1[i] && y2[i] <= yr)
rez = gcd2(rez, buckRez[i]);
else if(!(yr < y1[i] || y2[i] < yl)) {
for(int j = i * LILBUCK; j < (i + 1) * LILBUCK; ++j)
if(yl <= cell[j].c && cell[j].c <= yr)
rez = gcd2(rez, cell[j].val);
}
return rez;
}
void debug() {
printf("number of cells in bucket: %d; number of bucklets: %d\n", sizebuck, nrb);
printf("Row bounds %d %d\n", x1, x2);
for(int i = 0; i < sizebuck; ++i)
printf("Cell %d-> %d %d %lld\n", i, cell[i].r, cell[i].c, cell[i].val);
for(int j = 0; j < nrb; ++j) {
printf("Bucklet %d; bounds: %d %d; gcd: %lld\n", j, y1[j], y2[j], buckRez[j]);
}
}
};
map<pair<int, int>, long long> cellMap;
set<Cell> cells;
struct ThisIsEpic {
int nrcells, nrb;
Cell cell[MAX_N];
Bucket dothe[MAX_N / BIGBUCK + 1];
void init() {
nrcells = nrb = 0;
}
void pushCell(Cell x) {
if(nrcells % BIGBUCK == 0) {
dothe[nrb].init();
dothe[nrb].x1 = x.r;
nrb++;
}
dothe[nrb - 1].x2 = x.r;
dothe[nrb - 1].pushCell(x);
cell[nrcells++] = x;
}
void build() {
this->init();
int i = 0;
for(auto it: cells)
pushCell(it);
for(int i = 0; i < nrb; ++i)
dothe[i].build();
}
long long BenShapiro(int xl, int xr, int yl, int yr) {
long long rez = 0LL;
for(int i = 0; i < nrb; ++i)
if(xl <= dothe[i].x1 && dothe[i].x2 <= xr)
rez = gcd2(rez, dothe[i].stankyleg(yl, yr));
else if(!(xr < dothe[i].x1 || dothe[i].x2 < xl)) {
for(int j = 0; j < dothe[i].sizebuck; ++j)
if(xl <= dothe[i].cell[j].r && dothe[i].cell[j].r <= xr &&
yl <= dothe[i].cell[j].c && dothe[i].cell[j].c <= yr)
rez = gcd2(rez, dothe[i].cell[j].val);
}
return rez;
}
void debug() {
printf("Number of cells: %d\nNumber of buckets: %d\n", nrcells, nrb);
for(int i = 0; i < nrb; ++i) {
printf("BUCKET %d\n", i);
dothe[i].debug();
}
printf("------------------------------------------------------------------\n");
}
} xdxd;
void init(int _R, int _C) {
R = _R;
C = _C;
}
void update(int P, int Q, long long K) {
//printf("UPDATE: %d %d %lld\n", P, Q, K);
if(cellMap[make_pair(P, Q)] != 0)
cells.erase({P, Q, cellMap[make_pair(P, Q)] - 1});
cells.insert({P, Q, K});
cellMap[make_pair(P, Q)] = K + 1;
//printf("CELLS!!!!!!\n");
//for(auto it: cells)
// printf("%d %d %d\n", it.r, it.c, it.val);
//printf("/CELLS\n");
xdxd.build();
//xdxd.debug();
}
long long calculate(int P, int Q, int U, int V) {
return xdxd.BenShapiro(P, U, Q, V);
}
