#include "game.h"
#include <vector>
typedef long long ll;
using namespace std;
vector <vector<ll>> tree;
ll TTree[10000000];
ll b[100][100];
ll block = 45;
ll a[4000][4000];
int H, W;
ll __gcd(ll a, ll b) {
while (a && b) {
(a > b) ? a %= b : b %= a;
}
return a + b;
}
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));
}
ll GCDOFLIST(vector<ll> u) {
ll k = 0;
for (int i = 0; i < (int)u.size(); i++) {
k = __gcd(u[i], k);
}
return k;
}
void Update_(int v, int x1, int y1, int x2, int y2, int R, int C, ll val) {
if (x1 > x2) return;
if (y1 > y2) return;
bool ch = false;
if (x1 <= R && R <= x2 && y1 <= C && C <= y2) ch = true;
if (!ch) return;
if (x1 == x2 && y1 == y2) {
TTree[v] = val;
return;
}
int mx = (x1 + x2) / 2;
int my = (y1 + y2) / 2;
Update_(4 * v, x1, y1, mx, my, R, C, val);
Update_(4 * v + 1, x1, my + 1, mx, y2, R, C, val);
Update_(4 * v + 2, mx + 1, y1, x2, my, R, C, val);
Update_(4 * v + 3, mx + 1, my + 1, x2, y2, R, C, val);
TTree[v] = 0;
TTree[v] = __gcd(TTree[v], TTree[4 * v]);
TTree[v] = __gcd(TTree[v], TTree[4 * v + 1]);
TTree[v] = __gcd(TTree[v], TTree[4 * v + 2]);
TTree[v] = __gcd(TTree[v], TTree[4 * v + 3]);
}
ll GCCCD(int v, int x1, int y1, int x2, int y2, int xx1, int yy1, int xx2, int yy2) {
if (x1 > x2) return 0;
if (y1 > y2) return 0;
if (x1 >= xx1 && y1 >= yy1 && x2 <= xx2 && y2 <= yy2) {
return TTree[v];
}
bool ch = true;
if (xx1 > x2) ch = false;
if (xx2 < x1) ch = false;
if (yy1 > y2) ch = false;
if (yy2 < y1) ch = false;
if (!ch) return 0;
int mx = (x1 + x2) / 2;
int my = (y1 + y2) / 2;
return GCDOFLIST({ GCCCD(4 * v, x1, y1, mx, my, xx1, yy1, xx2, yy2),
GCCCD(4 * v + 1, x1, my + 1, mx, y2, xx1, yy1, xx2, yy2),
GCCCD(4 * v + 2, mx + 1, y1, x2, my, xx1, yy1, xx2, yy2),
GCCCD(4 * v + 3, mx + 1, my + 1, x2, y2, xx1, yy1, xx2, yy2) });
}
void init(int R, int C) {
H = R;
W = C;
tree.resize(R);
for (int i = 0; i < R; i++) {
tree[i].resize(4 * C);
}
}
void update(int R, int Q, ll K) {
if (max(H, W) <= 100) {
a[R][Q] = K;
return;
}
Update_(1, 0, 0, H - 1, W - 1, R, Q, K);
}
ll calculate(int P, int Q, int U, int V) {
if (max(H, W) <= 100) {
ll u = 0;
for (int i = P; i <= U; i++) {
for (int j = Q; j <= V; j++) {
u = __gcd(u, a[i][j]);
}
}
return u;
}
return GCCCD(1, 0, 0, H - 1, W - 1, P, Q, U, V);
}
