#include "game.h"
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 1'000'000'000;
ll gcd2(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct col_tree
{
int l;
int r;
ll g = 0;
col_tree* left = NULL;
col_tree* right = NULL;
};
col_tree* col_stash = new col_tree[3'000'000];
int col_tree_ct = -1;
col_tree* new_col_tree(int L, int R)
{
col_tree_ct++;
col_stash[col_tree_ct].l = L;
col_stash[col_tree_ct].r = R;
return &col_stash[col_tree_ct];
}
void update(col_tree* T, int I, ll V)
{
if(T->l == T->r)
{
T->g = V;
}
else
{
if(I <= (T->l+T->r)/2)
{
if(T->left == NULL) T->left = new_col_tree(T->l, (T->l+T->r)/2);
update(T->left, I, V);
}
else
{
if(T->right == NULL) T->right = new_col_tree((T->l+T->r)/2+1, T->r);
update(T->right, I, V);
}
ll lg = (T->left == NULL) ? 0 : T->left->g;
ll rg = (T->right == NULL) ? 0 : T->right->g;
T->g = gcd2(lg, rg);
}
}
ll range_gcd(col_tree* T, int L, int R)
{
if(T == NULL) return 0;
else if(R < T->l || T->r < L) return 0;
else if(L <= T->l && T->r <= R) return T->g;
else return gcd2(range_gcd(T->left, L, R), range_gcd(T->right, L, R));
}
struct row_tree
{
int l;
int r;
};
col_tree* ST;
void init(int R, int C)
{
ST = new col_tree[R];
for(int r = 0; r < R; r++)
{
ST[r].l = 0;
ST[r].r = INF-1;
}
}
void update(int P, int Q, long long K)
{
update(&ST[P], Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
ll res = 0;
for(int r = P; r <= U; r++)
res = gcd2(res, range_gcd(&ST[r], Q, V));
/* ... */
return res;
}
