#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define f1 first
#define s2 second
using ii = pair<int, int>;
using ll = long long;
inline ll gcd(ll X, ll Y) {
ll tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
int R, C;
map<ll, ll> st;
void init(int r, int c)
{
R = r; C = c;
}
inline ll get(int a, int b)
{
if (!st.count(2ll * a*C + b))
return 0;
return st[2ll * a*C + b];
}
void update(int P, int Q, ll K)
{
int _P = P + R, _Q = Q + C;
for (int i = _P; i > 0; i >>= 1)
{
for (int j = _Q; j > 0; j >>= 1)
{
if (i == _P && j == _Q) st[2ll * i*C + j] = K;
else if (i == _P) st[2ll * i*C + j] = gcd(get(i, j << 1), get(i, j << 1 | 1));
else if (j == _Q) st[2ll * i*C + j] = gcd(get(i << 1, j), get(i << 1 | 1, j));
else st[2ll * i*C + j] = gcd(gcd(get(i, j << 1), get(i, j << 1 | 1)), gcd(get(i << 1, j), get(i << 1 | 1, j)));
}
}
}
ll calculate(int P, int Q, int U, int V)
{
ll res = 0;
for (P += R, U += R+1; P < U; P >>= 1, U >>= 1)
{
if (P & 1)
{
for (int l = Q+C, r = V+C+1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) res = gcd(res, get(P, l++));
if (r & 1) res = gcd(res, get(P, --r));
}
P++;
}
if (U & 1)
{
--U;
for (int l = Q+C, r = V+C+1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) res = gcd(res, get(U, l++));
if (r & 1) res = gcd(res, get(U, --r));
}
}
}
return res;
}
