#include "game.h"
#include <csignal>
#include <iostream>
#include <numeric>
#include <vector>
using i32 = int32_t;
using i64 = long long;
auto midpoint(i32 l, i32 r) -> i32 { return l + (r - l) / 2; }
struct Node1 {
Node1 *l, *r;
i32 from, to;
i64 val;
explicit Node1(i32 from, i32 to)
: l{nullptr}, r{nullptr}, from{from}, to{to}, val{0} {}
explicit Node1(i32 len) : Node1(0, len) {}
auto left() -> Node1 * { return l ?: l = new Node1(from, midpoint(from, to)); }
auto right() -> Node1 * { return r ?: r = new Node1(midpoint(from, to), to); }
void set(i32 pos, i64 i) {
if (to - from > 1) {
auto m = midpoint(from, to);
if (pos < m)
left()->set(pos, i);
else
right()->set(pos, i);
val = 0;
if (l)
val = std::gcd(val, l->val);
if (r)
val = std::gcd(val, r->val);
} else {
val = i;
}
}
auto query(i32 l, i32 r) -> i64 {
if (l <= from && to <= r) {
// std::cerr << "including " << from << ".." << to << "\n";
return val;
} else if (to <= l || r <= from) {
// std::cerr << "excluding " << from << ".." << to << "\n";
return 0;
} else {
return std::gcd(left()->query(l, r), right()->query(l, r));
}
}
};
struct Node2 {
Node2 *l, *r;
i32 from, to;
Node1 *val;
i32 width;
explicit Node2(i32 from, i32 to, i32 width)
: l{nullptr}, r{nullptr}, from{from}, to{to}, val{new Node1{width}},
width{width} {}
explicit Node2(i32 len, i32 width) : Node2(0, len, width) {}
auto left() -> Node2 * {
return l ?: l = new Node2(from, midpoint(from, to), width);
}
auto right() -> Node2 * {
return r ?: r = new Node2(midpoint(from, to), to, width);
}
void set(i32 R, i32 C, i64 i) {
if (to - from > 1) {
auto m = midpoint(from, to);
if (R < m)
left()->set(R, C, i);
else
right()->set(R, C, i);
// Have to fix value for column c
auto fixed = 0;
if (l)
fixed = std::gcd(fixed, l->val->query(C, C + 1));
if (r)
fixed = std::gcd(fixed, r->val->query(C, C + 1));
val->set(C, fixed);
} else {
val->set(C, i);
}
}
auto query(i32 x1, i32 x2, i32 y1, i32 y2) -> i64 {
if (x1 <= from && to <= x2) {
return val->query(y1, y2);
} else if (to <= x1 || x2 <= from) {
return 0;
} else {
return std::gcd(left()->query(x1, x2, y1, y2),
right()->query(x1, x2, y1, y2));
}
}
};
namespace {
Node2 *st;
i32 h, w;
} // namespace
void init(i32 R, i32 C) {
st = new Node2{R, C};
h = R;
w = C;
}
void update(i32 P, i32 Q, i64 K) { st->set(P, Q, K); }
auto calculate(i32 P, i32 Q, i32 U, i32 V) -> i64 {
return st->query(P, U + 1, Q, V + 1);
}
