#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int const R = 1 << 30, C = 1 << 30;
// ^ really good programming language
struct NodeX
{
int xChildren, yRoot;
};
struct NodeY
{
int yChildren;
long long g;
};
NodeX *root;
int allocNode(size_t s) { return (int)((char *)calloc(1, s) - (char *)root); }
char *getYRoot(void *z) { return ((char *)root + *((int *)z + 1)); }
char *getLeftChild(void *z) { return ((char *)root + *(int *)z); }
long long calculateY(int Q, int V, NodeY *z, int A, int B)
{
if (B < Q || A > V)
return 0;
if (Q <= A && B <= V)
return z->g;
if (z->yChildren)
return gcd(calculateY(Q, V, (NodeY *)getLeftChild(z), A, (A + B) / 2),
calculateY(Q, V, (NodeY *)getLeftChild(z) + 1, (A + B) / 2 + 1, B));
return 0;
}
long long calculateX(int P, int Q, int U, int V, NodeX *z, int A, int B)
{
if (B < P || A > U)
return 0;
if (P <= A && B <= U)
return z->yRoot ? calculateY(Q, V, (NodeY *)getYRoot(z), 0, C - 1) : 0;
if (z->xChildren)
return gcd(calculateX(P, Q, U, V, (NodeX *)getLeftChild(z), A, (A + B) / 2),
calculateX(P, Q, U, V, (NodeX *)getLeftChild(z) + 1, (A + B) / 2 + 1, B));
return 0;
}
void updateY(int Q, long long K, NodeY *z, int A, int B)
{
if (A == B)
{
z->g = K;
return;
}
if (!z->yChildren)
z->yChildren = allocNode(2 * sizeof(NodeY));
if (Q <= (A + B) / 2)
updateY(Q, K, (NodeY *)getLeftChild(z), A, (A + B) / 2);
else
updateY(Q, K, (NodeY *)getLeftChild(z) + 1, (A + B) / 2 + 1, B);
z->g = gcd(((NodeY *)getLeftChild(z))->g, ((NodeY *)getLeftChild(z) + 1)->g);
}
void updateX(int P, int Q, long long K, NodeX *z, int A, int B)
{
if (!z->yRoot)
z->yRoot = allocNode(sizeof(NodeY));
if (A == B)
{
updateY(Q, K, (NodeY *)getYRoot(z), 0, C - 1);
return;
}
if (!z->xChildren)
z->xChildren = allocNode(2 * sizeof(NodeX));
if (P <= (A + B) / 2)
updateX(P, Q, K, (NodeX *)getLeftChild(z), A, (A + B) / 2);
else
updateX(P, Q, K, (NodeX *)getLeftChild(z) + 1, (A + B) / 2 + 1, B);
long long g = 0;
if (((NodeX *)getLeftChild(z))->yRoot)
g = gcd(g, calculateY(Q, Q, (NodeY *)getYRoot(getLeftChild(z)), 0, C - 1));
if ((((NodeX *)getLeftChild(z)) + 1)->yRoot)
g = gcd(g, calculateY(Q, Q, (NodeY *)getYRoot((NodeX *)getLeftChild(z) + 1), 0, C - 1));
updateY(Q, g, (NodeY *)getYRoot(z), 0, C - 1);
}
void init(int R, int C) { root = (NodeX *)calloc(1, sizeof *root); }
void update(int P, int Q, long long K)
{
updateX(P, Q, K, root, 0, R - 1);
}
long long calculate(int P, int Q, int U, int V)
{
return calculateX(P, Q, U, V, root, 0, R - 1);
}
