#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
void init(int R, int C)
{
/* ... */
}
const int maxc = 1e9 + 10;
struct vertex
{
vertex *lc, *rc;
set < pair < int, ll > > values;
vertex()
{
lc = rc = NULL;
values.clear();
}
};
vertex *tree = new vertex();
void make_kids(vertex *root)
{
if (root -> lc == NULL)
root -> lc = new vertex();
if (root -> rc == NULL)
root -> rc = new vertex();
}
void add_to_vertex(vertex *root, pair < int, ll > val)
{
root -> values.insert(val);
}
void remove_from_vertex(vertex *root, pair < int, ll > val)
{
root -> values.erase(val);
}
void add_val(vertex *root, int left, int right, int pivot, pair < int, ll > val)
{
///cout << "add val " << left << " " << right << " " << pivot << endl;
add_to_vertex(root, val);
///cout << "fine" << endl;
if (left == right)
return;
make_kids(root);
int mid = (left + right) / 2;
if (pivot <= mid)
add_val(root -> lc, left, mid, pivot, val);
else
add_val(root -> rc, mid + 1, right, pivot, val);
}
void remove_val(vertex *root, int left, int right, int pivot, pair < int, ll > val)
{
remove_from_vertex(root, val);
if (left == right)
return;
///make_kids(root);
int mid = (left + right) / 2;
if (pivot <= mid)
remove_val(root -> lc, left, mid, pivot, val);
else
remove_val(root -> rc, mid + 1, right, pivot, val);
}
map < pair < int, int >, ll > board;
void update(int P, int Q, long long K)
{
//cout << "update " << P << " " << Q << " " << K << endl;
if (board.count({P, Q}))
remove_val(tree, 0, maxc, P, {Q, board[{P, Q}]});
// cout << "Survive" << endl;
board[{P, Q}] = K;
add_val(tree, 0, maxc, P, {Q, K});
///cout << "Fuck" << endl;
/* ... */
}
ll query_vertex(vertex *root, int dw, int up)
{
ll res = 0;
for (pair < int, ll > cur : root -> values)
{
if (cur.first >= dw && cur.first <= up)
res = gcd2(res, cur.second);
}
return res;
}
ll query(vertex *root, int left, int right, int qleft, int qright, int kmin, int kmax)
{
if (root == NULL || left > qright || right < qleft)
return 0;
if (left >= qleft && right <= qright)
{
return query_vertex(root, kmin, kmax);
}
int mid = (left + right) / 2;
return gcd2(query(root -> lc, left, mid, qleft, qright, kmin, kmax),
query(root -> rc, mid + 1, right, qleft, qright, kmin, kmax));
}
long long calculate(int P, int Q, int U, int V)
{
/**map < pair < int, int >, ll > :: iterator it;
ll res = 0;
for (it = board.begin(); it != board.end(); it ++)
{
pair < int, int > cor = it -> first;
if (cor.first >= P && cor.first <= U &&
cor.second >= Q && cor.second <= V)
{
res = __gcd(res, it -> second);
}
}*/
/* ... */
return query(tree, 0, maxc, P, U, Q, V);
}
