#include <stdio.h>
#include <algorithm>
#include "game.h"
#define getchar getchar_unlocked
#define putchar putchar_unlocked
typedef long long i64;
i64 gcd(i64 a, i64 b)
{
// a = std::abs(a), b = std::abs(b);
if (!a || !b)
return a | b;
int az = __builtin_ctzll(a), bz = __builtin_ctzll(b), z = std::min(az, bz);
b >>= bz;
while (a)
{
a >>= az;
i64 d = std::abs(a - b);
az = __builtin_ctzll(d);
if (a < b)
b = a;
a = d;
}
return b << z;
}
const int N = 22010, V = 1000000010, LOG_V = 30;
// Dynamic 2D seg
// exterior : x inner : y
namespace dyna_seg_2d
{
int XL, XR, YL, YR;
void init(int _XL, int _XR, int _YL, int _YR) { XL = _XL, XR = _XR, YL = _YL, YR = _YR; }
int root;
struct node_x
{
int lc, rc;
int rt; // root for inner dimension
} ptx[N * (LOG_V + 1)];
int cnt_x;
struct node_y
{
int lc, rc;
i64 sum; // real info in inner
} pty[N * (LOG_V + 1) * (LOG_V + 1)];
int cnt_y;
void pushup_y(int u) { pty[u].sum = gcd(pty[pty[u].lc].sum, pty[pty[u].rc].sum); }
void modify_y(int& u, int yl, int yr, const int& x, const int& y, const i64& val)
{
if (!u)
u = ++cnt_y;
if (yl == yr)
{
pty[u].sum = val;
return;
}
int ym = (yl + yr) >> 1;
if (y <= ym)
modify_y(pty[u].lc, yl, ym, x, y, val);
else
modify_y(pty[u].rc, ym + 1, yr, x, y, val);
pushup_y(u);
}
void pushup_x(int &u, int xlc, int xrc, int yl, int yr, int y)
{
if (!u)
u = ++cnt_y;
if (yl == yr)
{
pty[u].sum = gcd(pty[xlc].sum, pty[xrc].sum);
return;
}
int ym = (yl + yr) >> 1;
if (y <= ym)
pushup_x(pty[u].lc, pty[xlc].lc, pty[xrc].lc, yl, ym, y);
else
pushup_x(pty[u].rc, pty[xlc].rc, pty[xrc].rc, ym + 1, yr, y);
pushup_y(u);
}
void modify_x(int& u, int xl, int xr, const int& x, const int& y, const i64& val)
{
if (!u) // dynamic add
u = ++cnt_x;
if (xl == xr)
{
modify_y(ptx[u].rt, YL, YR, x, y, val);
return;
}
int xm = (xl + xr) >> 1;
if (x <= xm)
modify_x(ptx[u].lc, xl, xm, x, y, val);
else
modify_x(ptx[u].rc, xm + 1, xr, x, y, val);
pushup_x(ptx[u].rt, ptx[ptx[u].lc].rt, ptx[ptx[u].rc].rt, YL, YR, y);
}
// [y1, y2] for query [yl, yr] for cur node
i64 query_y(int u, int yl, int yr, const int& y1, const int& y2)
{
if (yr < y1 || yl > y2 || !u)
return 0;
if (y1 <= yl && yr <= y2)
return pty[u].sum;
int ym = (yl + yr) >> 1;
return gcd(query_y(pty[u].lc, yl, ym, y1, y2), query_y(pty[u].rc, ym + 1, yr, y1, y2));
}
i64 query_x(int u, int xl, int xr, const int& x1, const int& x2, const int& y1, const int& y2)
{
if (xr < x1 || xl > x2 || !u)
return 0;
if (x1 <= xl && xr <= x2)
return query_y(ptx[u].rt, YL, YR, y1, y2);
int xm = (xl + xr) >> 1;
return gcd(query_x(ptx[u].lc, xl, xm, x1, x2, y1, y2), query_x(ptx[u].rc, xm + 1, xr, x1, x2, y1, y2));
}
void modify(int x, int y, i64 val) { modify_x(root, XL, XR, x, y, val); }
i64 query(int x1, int x2, int y1, int y2) { return query_x(root, XL, XR, x1, x2, y1, y2); }
}
void init(int R, int C) { dyna_seg_2d::init(0, R - 1, 0, C - 1); }
void update(int P, int Q, i64 K) { dyna_seg_2d::modify(P, Q, K); }
i64 calculate(int P, int Q, int U, int V) { return dyna_seg_2d::query(P, U, Q, V); }
