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