#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const ll inf = 1e18;
struct node {
int tar, need;
ll sum;
node() {
tar = -1;
}
node(int _tar, int _need, ll _sum) {
tar = _tar; need = _need; sum = _sum;
}
};
int n;
const int lg = 24;
vector<vector<node>> jump1, jump2;
vector<vector<vector<node>>> jump;
vector<int> s, p, w, l;
vector<int> pw;
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
pw = {1};
for (int i = 1; i < 8; i++) pw.emplace_back(pw.back() * 8);
s = _s; p = _p; w =_w; l = _l;
n = _n;
jump1 = vector(lg, vector(n, node()));
jump = vector(lg / 3, vector(lg, vector(n, node())));
for (int i = 0; i < n; i++) {
jump1[0][i] = node(w[i], s[i], s[i]);
}
for (int j = 1; j < lg; j++) {
for (int i = 0; i < n; i++) {
if (jump1[j - 1][i].tar == n) jump1[j][i] = jump1[j - 1][i];
else {
auto &par = jump1[j - 1][jump1[j - 1][i].tar];
jump1[j][i].tar = par.tar;
jump1[j][i].sum = jump1[j - 1][i].sum + par.sum;
jump1[j][i].need = max(jump1[j - 1][i].need, par.need - (int) min(jump1[j - 1][i].sum, (ll) 1e9));
}
}
}
for (int x = 0; x < jump.size(); x++) {
for (int i = 0; i < n; i++) {
if (s[i] <= pw[x]) jump[x][0][i] = node(w[i], 1e9, s[i]);
else jump[x][0][i] = node(l[i], s[i], p[i]);
}
for (int j = 1; j < lg; j++) {
for (int i = 0; i < n; i++) {
if (jump[x][j - 1][i].tar == n) {
jump[x][j][i] = jump[x][j - 1][i];
continue;
}
auto &par = jump[x][j - 1][jump[x][j - 1][i].tar];
jump[x][j][i] = node(par.tar, 0, par.sum + jump[x][j - 1][i].sum);
jump[x][j][i].need = min(jump[x][j - 1][i].need, par.need - (int) min(jump[x][j - 1][i].sum, ll(1e9)));
}
}
}
}
long long simulate(int x, int z) {
ll now = z;
while (x != n) {
for (int i = lg - 1; i >= 0 and x < n; i--) {
if (jump1[i][x].need <= now) {
now += jump1[i][x].sum;
x = jump1[i][x].tar;
}
}
if (x == n) break;
assert(jump1[0][x].need > now);
int wh = (31 - __builtin_clz(now)) / 3;
if (wh >= lg) return 0;
for (int i = lg - 1; i >= 0 and x < n; i--) {
if (now >= jump[wh][i][x].need) continue;
now += jump[wh][i][x].sum;
x = jump[wh][i][x].tar;
}
if (x == n) break;
if (now >= s[x]) now += s[x], x = w[x];
else now += p[x], x = l[x];
}
return now;
}
