#include "dungeons.h"
#include <bits/stdc++.h>
using ll = long long;
using std::vector;
struct dungeon {
int s, p, w, l;
};
struct info {
int pos, thres;
ll sum;
info() = default;
};
constexpr int LOG = 24;
int size;
vector<dungeon> data;
vector<info> lift[LOG][LOG];
vector<info> win_all[LOG];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
size = n;
data.reserve(n);
for (int i = 0; i < n; ++i) {
data.push_back({s[i], p[i], w[i], l[i]});
}
for (int stage = 0; stage < LOG; ++stage) {
lift[stage][0].resize(n + 1);
const int lb = 1 << stage;
const int ub = 1 << (stage + 1);
for (int i = 0; i < n; ++i) {
if (s[i] < lb) {
lift[stage][0][i] = {w[i], std::max(0, ub - s[i]), s[i]};
} else if (s[i] >= ub) {
lift[stage][0][i] = {l[i], std::max(0, ub - p[i]), p[i]};
} else {
lift[stage][0][i] = {l[i], std::max(0, std::min(s[i], ub - p[i])), p[i]};
}
}
lift[stage][0][n] = {n, 0, 0};
for (int k = 0; k < stage; ++k) {
lift[stage][k + 1].resize(n + 1);
for (int i = 0; i <= n; ++i) {
const auto [p0, t0, s0] = lift[stage][k][i];
const auto [p1, t1, s1] = lift[stage][k][p0];
lift[stage][k + 1][i] = {p1, s0 >= t1 ? 0 : std::min<int>(t0, t1 - s0), s0 + s1};
}
}
}
win_all[0].resize(n + 1);
for (int i = 0; i < n; ++i) {
win_all[0][i] = {w[i], 0, s[i]};
}
win_all[0][n] = {n, 0, 0};
for (int k = 0; k < LOG - 1; ++k) {
win_all[k + 1].resize(n + 1);
for (int i = 0; i <= n; ++i) {
const auto [p0, t0, s0] = win_all[k][i];
const auto [p1, t1, s1] = win_all[k][p0];
win_all[k + 1][i] = {p1, 0, s0 + s1};
}
}
}
ll simulate(int x, int z) {
int stage = 0;
while (true) {
while (z >= (1 << (stage + 1))) {
stage += 1;
}
if (x == size) {
return z;
}
if (stage >= LOG) {
break;
}
for (int k = stage; k >= 0; --k) {
if (lift[stage][k][x].pos != size and z < lift[stage][k][x].thres) {
z += lift[stage][k][x].sum;
x = lift[stage][k][x].pos;
}
}
if (z >= data[x].s) {
z += data[x].s;
x = data[x].w;
} else {
z += data[x].p;
x = data[x].l;
}
}
ll ret = z;
for (int k = LOG - 1; k >= 0; --k) {
if (win_all[k][x].pos != size) {
ret += win_all[k][x].sum;
x = win_all[k][x].pos;
}
}
ret += data[x].s;
return ret;
}
