#include "game.h"
#include <stdio.h>
#include <cassert>
typedef struct nodeX nodeX;
typedef struct nodeY nodeY;
struct nodeX
{
nodeX* l;
nodeX* r;
nodeY* y;
nodeX()
{
l = NULL;
r = NULL;
y = NULL;
}
};
struct nodeY
{
long long v = 0;
nodeY* l;
nodeY* r;
nodeY()
{
l = NULL;
r = NULL;
}
};
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;
}
int maxR, maxC;
nodeX* root;
void init(int R, int C)
{
maxR = R - 1;
maxC = C - 1;
root = new nodeX();
}
void updateY(nodeY* p, nodeY* l, nodeY* r, int Q, long long K, int sY, int eY)
{
// printf("updateY %p %d %lld %d %d\n", p, Q, K, sY, eY);
if (sY == eY)
{
if (l == NULL && r == NULL)
p->v = K;
else if (l == NULL)
p->v = r->v;
else if (r == NULL)
p->v = l->v;
else
p->v = gcd2(l->v, r->v);
return;
}
int m = (sY + eY)/2;
if (Q <= m)
{
if (p->l == NULL)
p->l = new nodeY();
updateY(p->l, (l == NULL)?NULL:l->l, (r == NULL)?NULL:r->l, Q, K, sY, m);
}
else
{
if (p->r == NULL)
p->r = new nodeY();
updateY(p->r, (l == NULL)?NULL:l->r, (r == NULL)?NULL:r->r, Q, K, m + 1, eY);
}
if (p->l == NULL && p->r == NULL)
while (1);
else if (p->l == NULL)
p->v = p->r->v;
else if (p->r == NULL)
p->v = p->l->v;
else
p->v = gcd2(p->l->v, p->r->v);
// printf("sY %d eY %d %d\n", sY, eY, p->v);
}
void updateX(nodeX* p, int P, int Q, long long K, int sX, int eX)
{
// printf("updateX %p %d %d %lld %d %d\n", p, P, Q, K, sX, eX);
if (sX == eX)
{
if (p->y == NULL)
p->y = new nodeY();
updateY(p->y, NULL, NULL, Q, K, 0, maxC);
return;
}
int m = (sX + eX)/2;
if (P <= m)
{
if (p->l == NULL)
p->l = new nodeX();
updateX(p->l, P, Q, K, sX, m);
}
else
{
if (p->r == NULL)
p->r = new nodeX();
updateX(p->r, P, Q, K, m + 1, eX);
}
if (p->y == NULL)
p->y = new nodeY();
updateY(p->y, (p->l == NULL)?NULL:p->l->y, (p->r == NULL)?NULL:p->r->y, Q, K, 0, maxC);
}
void update(int P, int Q, long long K)
{
updateX(root, P, Q, K, 0, maxR);
}
int min(int a, int b)
{
return (a < b)?a:b;
}
int max(int a, int b)
{
return (a > b)?a:b;
}
long long queryY(nodeY* p, int qsY, int qeY, int sY, int eY)
{
// printf("queryY %p %d %d %d %d\n", p, qsY, qeY, sY, eY);
if (qsY == sY && qeY == eY)
return p->v;
int m = (sY + eY)/2;
long long r = 0;
if (qsY <= m)
{
if (p->l != NULL)
r = gcd2(r, queryY(p->l, qsY, min(qeY, m), sY, m));
}
if (qeY >= m + 1)
{
if (p->r != NULL)
r = gcd2(r, queryY(p->r, max(qsY, m + 1), qeY, m + 1, eY));
}
// printf("%lld\n", r);
return r;
}
long long queryX(nodeX* p, int qsX, int qeX, int qsY, int qeY, int sX, int eX)
{
// printf("queryX %p %d %d %d %d %d %d\n", p, qsX, qeX, qsY, qeY, sX, eX);
if (qsX == sX && qeX == eX)
{
if (p->y == NULL)
return 0;
return queryY(p->y, qsY, qeY, 0, maxC);
}
int m = (sX + eX)/2;
long long r = 0;
if (qsX <= m)
{
if (p->l != NULL)
r = gcd2(r, queryX(p->l, qsX, min(qeX, m), qsY, qeY, sX, m));
}
if (qeX >= m + 1)
{
if (p->r != NULL)
r = gcd2(r, queryX(p->r, max(qsX, m + 1), qeX, qsY, qeY, m + 1, eX));
}
// printf("%d %d %lld\n", sX, eX, r);
return r;
}
long long calculate(int P, int Q, int U, int V)
{
return queryX(root, P, U, Q, V, 0, maxR);
}
