#include "game.h"
#include <vector>
typedef long long ll;
using namespace std;
const int N = 2023, M = 2023;
ll TTree[11][400400], tree[N][4 * M], tree2[N][4 * M], tree3[N][4 * M];
int block = 46;
int H, W;
ll __gcd(ll a, ll b) {
while (a && b) {
(a > b) ? a %= b : b %= a;
}
return a + b;
}
void Upd(int R, int C, ll value, int v, int tl, int tr) {
if (tl > C || tr < C) {
return;
}
if (tl == tr) {
TTree[R][v] = value;
return;
}
int tm = (tl + tr) / 2;
Upd(R, C, value, 2 * v, tl, tm);
Upd(R, C, value, 2 * v + 1, tm + 1, tr);
TTree[R][v] = __gcd(TTree[R][2 * v], TTree[R][2 * v + 1]);
}
ll _GCD_(int R, int v, int tl, int tr, int l, int r) {
if (tl >= l && tr <= r) return TTree[R][v];
if (tl > r || tr < l) return 0;
int tm = (tl + tr) / 2;
return __gcd(_GCD_(R, 2 * v, tl, tm, l, r),
_GCD_(R, 2 * v + 1, tm + 1, tr, l, r));
}
void update1(int R, int C, ll value, int v, int tl, int tr) {
if (tl > C || tr < C) {
return;
}
if (tl == tr) {
tree[R][v] = value;
return;
}
int tm = (tl + tr) / 2;
update1(R, C, value, 2 * v, tl, tm);
update1(R, C, value, 2 * v + 1, tm + 1, tr);
tree[R][v] = __gcd(tree[R][2 * v], tree[R][2 * v + 1]);
}
ll GCD(int R, int v, int tl, int tr, int l, int r) {
if (tl >= l && tr <= r) return tree[R][v];
if (tl > r || tr < l) return 0;
int tm = (tl + tr) / 2;
return __gcd(GCD(R, 2 * v, tl, tm, l, r),
GCD(R, 2 * v + 1, tm + 1, tr, l, r));
}
void update2(int R, int C, ll value, int v, int tl, int tr) {
if (tl > R || tr < R) {
return;
}
if (tl == tr) {
tree2[C][v] = value;
return;
}
int tm = (tl + tr) / 2;
update2(R, C, value, 2 * v, tl, tm);
update2(R, C, value, 2 * v + 1, tm + 1, tr);
tree2[C][v] = __gcd(tree2[C][2 * v], tree2[C][2 * v + 1]);
}
ll GCD2(int C, int v, int tl, int tr, int l, int r) {
if (tl >= l && tr <= r) return tree2[C][v];
if (tl > r || tr < l) return 0;
int tm = (tl + tr) / 2;
return __gcd(GCD2(C, 2 * v, tl, tm, l, r),
GCD2(C, 2 * v + 1, tm + 1, tr, l, r));
}
void update3(int R, int C, ll value, int v, int tl, int tr) {
if (tl > C || tr < C) {
return;
}
if (tl == tr) {
tree3[R][v] = value;
return;
}
int tm = (tl + tr) / 2;
update3(R, C, value, 2 * v, tl, tm);
update3(R, C, value, 2 * v + 1, tm + 1, tr);
tree3[R][v] = __gcd(tree3[R][2 * v], tree3[R][2 * v + 1]);
}
ll GCD3(int R, int v, int tl, int tr, int l, int r) {
if (tl >= l && tr <= r) return tree3[R][v];
if (tl > r || tr < l) return 0;
int tm = (tl + tr) / 2;
return __gcd(GCD3(R, 2 * v, tl, tm, l, r),
GCD3(R, 2 * v + 1, tm + 1, tr, l, r));
}
void init(int R, int C) {
H = R;
W = C;
}
void update(int R, int Q, ll K) {
Upd(R, Q, K, 1, 0, W - 1);
if (H > 10) {
update1(R, Q, K, 1, 0, W - 1);
update2(R, Q, K, 1, 0, H - 1);
for (int i = max(0, R - block + 1); i <= min(R, H - block); i++) {
update3(i, Q, GCD2(Q, 1, 0, H - 1, i, i + block - 1), 1, 0, W - 1);
}
}
}
ll calculate(int P, int Q, int U, int V) {
ll u = 0;
if (H > 10) {
int i;
for (i = P; i + block - 1 <= U; i += block) {
u = __gcd(u, GCD3(i, 1, 0, W - 1, Q, V));
}
for (; i <= U; i++) {
u = __gcd(u, GCD(i, 1, 0, W - 1, Q, V));
}
}
else {
for (int i = P; i <= U; i++) {
u = __gcd(u, _GCD_(i, 1, 0, W - 1, Q, V));
}
}
return u;
}
