#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int T = 22003 * 30 * 30;
long long gcd(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;
map<pair<int, int>, ll> mp;
int zy;
int uly[T / 2], ury[T / 2];
ll g[T / 2];
int zx;
int uy[T / 30];
int ulx[T / 30], urx[T / 30];
void ubdy(int tlx, int trx, int tly, int try_, int x, int y, ll k, int posyl, int posyr, int posy)
{
if (trx - tlx + 1 <= 3 && try_ - tly + 1 <= 3)
{
g[posy] = 0;
for (int i = tlx; i <= trx; ++i)
{
for (int j = tly; j <= try_; ++j)
{
if (mp.find(m_p(i, j)) != mp.end())
g[posy] = gcd(g[posy], mp[m_p(i, j)]);
}
}
return;
}
if (tly == try_)
{
if (tlx == trx)
{
g[posy] = k;
return;
}
g[posy] = 0;
int m = (tlx + trx) / 2;
if (m - tlx + 1 <= 3)
{
for (int i = tlx; i <= m; ++i)
{
if (mp.find(m_p(i, tly)) != mp.end())
g[posy] = gcd(g[posy], mp[m_p(i, tly)]);
}
}
else
g[posy] = gcd(g[posy], g[posyl]);
if (trx - m <= 3)
{
for (int i = m + 1; i <= trx; ++i)
{
if (mp.find(m_p(i, tly)) != mp.end())
g[posy] = gcd(g[posy], mp[m_p(i, tly)]);
}
}
else
g[posy] = gcd(g[posy], g[posyr]);
return;
}
int m = (tly + try_) / 2;
if (y <= m)
{
if (!uly[posy])
uly[posy] = ++zy;
ubdy(tlx, trx, tly, m, x, y, k, uly[posyl], uly[posyr], uly[posy]);
}
else
{
if (!ury[posy])
ury[posy] = ++zy;
ubdy(tlx, trx, m + 1, try_, x, y, k, ury[posyl], ury[posyr], ury[posy]);
}
g[posy] = gcd(g[uly[posy]], g[ury[posy]]);
}
void ubdx(int tlx, int trx, int x, int y, ll k, int posx)
{
if (tlx == trx)
{
if (!uy[posx])
uy[posx] = ++zy;
ubdy(tlx, trx, 0, C - 1, x, y, k, 0, 0, uy[posx]);
return;
}
int m = (tlx + trx) / 2;
if (x <= m)
{
if (!ulx[posx])
ulx[posx] = ++zx;
ubdx(tlx, m, x, y, k, ulx[posx]);
}
else
{
if (!urx[posx])
urx[posx] = ++zx;
ubdx(m + 1, trx, x, y, k, urx[posx]);
}
if (!uy[posx])
uy[posx] = ++zy;
ubdy(tlx, trx, 0, C - 1, x, y, k, uy[ulx[posx]], uy[urx[posx]], uy[posx]);
}
ll qryy(int tlx, int trx, int tly, int try_, int ly, int ry, int posy)
{
if (ly > ry)
return 0;
//if (posy == 0)
// return 0;
if (tly == ly && try_ == ry)
{
if (trx - tlx + 1 <= 3 && try_ - tly + 1 <= 3)
{
ll g = 0;
for (int i = tlx; i <= trx; ++i)
{
for (int j = tly; j <= try_; ++j)
{
if (mp.find(m_p(i, j)) != mp.end())
g = gcd(g, mp[m_p(i, j)]);
}
}
return g;
}
return g[posy];
}
int m = (tly + try_) / 2;
return gcd(qryy(tlx, trx, tly, m, ly, min(m, ry), uly[posy]),
qryy(tlx, trx, m + 1, try_, max(m + 1, ly), ry, ury[posy]));
}
ll qryx(int tlx, int trx, int lx, int rx, int ly, int ry, int posx)
{
if (lx > rx)
return 0;
if (posx == 0)
return 0;
if (tlx == lx && trx == rx)
{
return qryy(tlx, trx, 0, C - 1, ly, ry, uy[posx]);
}
int m = (tlx + trx) / 2;
return gcd(qryx(tlx, m, lx, min(m, rx), ly, ry, ulx[posx]),
qryx(m + 1, trx, max(m + 1, lx), rx, ly, ry, urx[posx]));
}
void init(int R, int C)
{
::R = R;
::C = C;
++zx;
}
void update(int P, int Q, long long K)
{
mp[m_p(P, Q)] = K;
ubdx(0, R - 1, P, Q, K, 1);
}
long long calculate(int P, int Q, int U, int V)
{
return qryx(0, R - 1, P, U, Q, V, 1);
}
