#include "game.h"
#include <iostream>
#pragma GCC optimize("Os")
int n, m, q;
struct Nodey {
Nodey *l, *r;
long long gcd;
Nodey () {
l = r = NULL;
gcd = 0;
}
};
long long ans = 0;
struct Nodex {
Nodex *l, *r;
Nodey *root;
Nodex () {
root = NULL;
l = r = NULL;
}
} *root;
long long gcd2(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
void updateY (Nodey* nod, int st, int dr, int a, long long k);
long long getVal (Nodex * nod, int b) {
long long ans = 0;
if (nod == NULL)
return 0;
Nodey *root = nod->root;
int st = 1, dr = m;
while (root != NULL) {
if (st == dr) {
return root-> gcd;
}
int mid = (st + dr) / 2;
if (mid >= b) {
root = root->l;
dr = mid;
}
else {
root = root-> r;
st = mid + 1;
}
}
return 0;
}
void updateX (Nodex* nod, int st, int dr, int a, int b, long long k) {
if (nod == NULL)
return;
if (st == dr) {
if (nod->root == NULL)
nod->root = new Nodey();
updateY(nod->root, 1, m, b, k);
return;
}
int mid = (st + dr) / 2;
if (a <= mid) {
if (nod->l == NULL)
nod->l = new Nodex();
updateX(nod->l, st, mid, a, b, k);
}
else {
if (nod->r == NULL)
nod->r = new Nodex();
updateX(nod->r, mid + 1, dr, a, b, k);
}
if (nod->root == NULL)
nod->root = new Nodey();
updateY(nod->root, 1, m, b, gcd2(getVal(nod->l, b), getVal(nod->r, b)));
}
void updateY (Nodey* nod, int st, int dr, int a, long long k) {
if (nod == NULL)
return;
if (st == dr) {
nod->gcd = k;
return;
}
int mid = (st + dr) / 2;
if (a <= mid) {
if (nod->l == NULL)
nod->l = new Nodey();
updateY(nod->l, st, mid, a, k);
}
else {
if (nod->r == NULL)
nod->r = new Nodey();
updateY(nod->r, mid + 1, dr, a, k);
}
nod->gcd = gcd2((nod->l == NULL ? 0 : nod->l->gcd), (nod->r == NULL ? 0 : nod->r->gcd));
}
void queryY(Nodey *nod, int st, int dr, int a, int b);
void queryX (Nodex *nod, int st, int dr, int a, int b, int c, int d) {
if (nod == NULL)
return;
if (b < st || a > dr)
return;
if (a <= st && dr <= b) {
queryY(nod->root, 1, m, c, d);
return;
}
int mid = (st + dr) / 2;
queryX(nod->l, st, mid, a, b, c, d);
queryX(nod->r, mid + 1, dr, a, b, c, d);
}
void init (int R, int C) {
n = R;
m = C;
root = new Nodex();
}
void queryY(Nodey *nod, int st, int dr, int a, int b) {
if (nod == NULL)
return;
if (b < st || a > dr)
return;
if (a <= st && dr <= b) {
ans = gcd2(ans, nod->gcd);
return;
}
int mid = (st + dr) / 2;
queryY(nod->l, st, mid, a, b);
queryY(nod->r, mid + 1, dr, a, b);
}
void update (int p, int q, long long k) {
p++; q++;
updateX(root, 1, n, p, q, k);
}
long long calculate (int x1, int y1, int x2, int y2) {
ans = 0;
x1 ++; y1++; x2++; y2++;
queryX(root, 1, n, x1, x2, y1, y2);
return ans;
}
