#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
{
ll g = 0;
int left = -1;
int right = -1;
};
const int z = 8'000'000;
col_tree* col_stashA = new col_tree[z];
col_tree* col_stashB = new col_tree[6'000'000];
int col_tree_ct = -1;
col_tree* getmem(int a)
{
if(a < z) return &col_stashA[a];
else return &col_stashB[a-z];
}
int new_col_tree()
{
col_tree_ct++;
return col_tree_ct;
// return &col_stash[col_tree_ct];
}
void update(col_tree* T, int I, ll V, int l, int r)
{
if(l == r)
{
T->g = V;
}
else
{
if(I <= (l+r)/2)
{
if(T->left == -1) T->left = new_col_tree();
update(getmem(T->left), I, V, l, (l+r)/2);
}
else
{
if(T->right == -1) T->right = new_col_tree();
update(getmem(T->right), I, V, (l+r)/2+1, r);
}
ll lg = (T->left == -1) ? 0 : getmem(T->left)->g;
ll rg = (T->right == -1) ? 0 : getmem(T->right)->g;
T->g = gcd2(lg, rg);
}
}
void update(col_tree* T, int I, ll V)
{
update(T, I, V, 0, INF-1);
}
ll range_gcd(col_tree* T, int L, int R, int l, int r)
{
if(T == NULL) return 0;
else if(R < l || r < L) return 0;
else if(L <= l && r <= R) return T->g;
else
{
ll ans = 0;
if(T->left != -1) ans = gcd2(ans, range_gcd(getmem(T->left), L, R, l, (l+r)/2));
if(T->right != -1) ans = gcd2(ans, range_gcd(getmem(T->right), L, R, (l+r)/2+1, r));
return ans;
} //return gcd2(range_gcd(T->left, L, R, l, (l+r)/2), range_gcd(T->right, L, R, (l+r)/2+1, r));
}
ll range_gcd(col_tree* T, int L, int R)
{
return range_gcd(T, L, R, 0, INF-1);
}
struct row_tree
{
col_tree v{0, -1, -1};
row_tree* left = NULL;
row_tree* right = NULL;
};
row_tree* row_stash = new row_tree[850'000]; //IF NECESSARY CUT THIS!!!!
int row_tree_ct = -1;
row_tree* new_row_tree()
{
row_tree_ct++;
return &row_stash[row_tree_ct];
}
//ro
void update(row_tree* T, int I, int J, ll V, int l, int r)
{
if(l == r)
{
update(&T->v, J, V);
}
else
{
if(I <= (l+r)/2)
{
if(T->left == NULL) T->left = new_row_tree();
update(T->left, I, J, V, l, (l+r)/2);
}
else
{
if(T->right == NULL) T->right = new_row_tree();
update(T->right, I, J, V, (l+r)/2+1, r);
}
ll lg = (T->left == NULL) ? 0 : range_gcd(&T->left->v, J, J);
ll rg = (T->right == NULL) ? 0 : range_gcd(&T->right->v, J, J);
update(&T->v, J, gcd2(lg, rg));
}
}
void update(row_tree* T, int I, int J, ll V)
{
update(T, I, J, V, 0, INF-1);
}
ll grid_gcd(row_tree* T, int R1, int R2, int C1, int C2, int l, int r)
{
if(T == NULL) return 0;
else if(R2 < l || r < R1) return 0;
else if(R1 <= l && r <= R2) return range_gcd(&T->v, C1, C2);
else return gcd2(grid_gcd(T->left, R1, R2, C1, C2, l, (l+r)/2), grid_gcd(T->right, R1, R2, C1, C2, (l+r)/2+1, r));
}
ll grid_gcd(row_tree* T, int R1, int R2, int C1, int C2)
{
return grid_gcd(T, R1, R2, C1, C2, 0, INF-1);
}
row_tree ST;
void init(int R, int C)
{
;
}
void update(int P, int Q, long long K)
{
update(&ST, P, Q, K);
}
ll calculate(int P, int Q, int U, int V)
{
return grid_gcd(&ST, P, U, Q, V);
}
