#include <bits/stdc++.h>
#include "game.h"
using namespace std;
int const R = 1 << 30, C = 1 << 30;
// ^ really good programming language
struct NodeY
{
unique_ptr<NodeY> l, r;
long long g;
void update(int Q, long long K, int A, int B)
{
if (A == B)
{
g = K;
return;
}
if (Q <= (A + B) / 2)
(l ? l : l = make_unique<NodeY>())->update(Q, K, A, (A + B) / 2);
else
(r ? r : r = make_unique<NodeY>())->update(Q, K, (A + B) / 2 + 1, B);
g = gcd(l ? l->g : 0, r ? r->g : 0);
}
long long calculate(int Q, int V, int A, int B)
{
if (B < Q || A > V)
return 0;
if (Q <= A && B <= V)
return g;
return gcd(l ? l->calculate(Q, V, A, (A + B) / 2) : 0,
r ? r->calculate(Q, V, (A + B) / 2 + 1, B) : 0);
}
};
struct NodeX
{
unique_ptr<NodeX> l, r;
unique_ptr<NodeY> y;
void update(int P, int Q, long long K, int A, int B)
{
if (!y)
y = make_unique<NodeY>();
if (A == B)
{
y->update(Q, K, 0, C - 1);
return;
}
if (P <= (A + B) / 2)
(l ? l : l = make_unique<NodeX>())->update(P, Q, K, A, (A + B) / 2);
else
(r ? r : r = make_unique<NodeX>())->update(P, Q, K, (A + B) / 2 + 1, B);
y->update(Q,
gcd(l && l->y ? l->y->calculate(Q, Q, 0, C - 1) : 0,
r && r->y ? r->y->calculate(Q, Q, 0, C - 1) : 0),
0, C - 1);
}
long long calculate(int P, int Q, int U, int V, int A, int B)
{
if (B < P || A > U)
return 0;
if (P <= A && B <= U)
return y ? y->calculate(Q, V, 0, C - 1) : 0;
return gcd(l ? l->calculate(P, Q, U, V, A, (A + B) / 2) : 0,
r ? r->calculate(P, Q, U, V, (A + B) / 2 + 1, B) : 0);
}
};
NodeX root;
void init(int R, int C) {}
void update(int P, int Q, long long K) { root.update(P, Q, K, 0, R - 1); }
long long calculate(int P, int Q, int U, int V) { return root.calculate(P, Q, U, V, 0, R - 1); }
