#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 400005, LOG = 24, LLOG = 8;
vt<int> S, P, W, L;
int N;
int lift[LLOG+1][mxN][LOG+1];
ll lift_val[LLOG+1][mxN][LOG+1];
ll lift_cap[LLOG+1][mxN][LOG+1];
ll depth[mxN];
ll simulate(int i, int zz) {
ll z = zz;
FOR(x, 0, LLOG) {
while (i != N && z < 1 << 3*(x+1)) {
ROF(j, LOG, 0)
if (z < lift_cap[x][i][j]) {
z += lift_val[x][i][j];
i = lift[x][i][j];
}
z += S[i];
i = W[i];
}
}
return z + depth[i];
}
void init(int _N, vt<int> _S, vt<int> _P, vt<int> _W, vt<int> _L) {
N = _N, S = _S, P = _P, W = _W, L = _L;
S.push_back(0);
P.push_back(0);
W.push_back(N);
L.push_back(N);
ROF(i, N-1, 0)
depth[i] = depth[W[i]] + S[i];
FOR(x, 0, LLOG) {
FOR(i, 0, N) {
if (S[i] > 1 << 3*x) {
lift[x][i][0] = L[i];
lift_val[x][i][0] = P[i];
lift_cap[x][i][0] = S[i];
} else {
lift[x][i][0] = W[i];
lift_val[x][i][0] = S[i];
lift_cap[x][i][0] = LLONG_MAX;
}
}
FOR(j, 1, LOG)
FOR(i, 0, N) {
lift[x][i][j] = lift[x][lift[x][i][j-1]][j-1];
lift_val[x][i][j] = lift_val[x][lift[x][i][j-1]][j-1] + lift_val[x][i][j-1];
lift_cap[x][i][j] = min(lift_cap[x][i][j-1], lift_cap[x][lift[x][i][j-1]][j-1] - lift_val[x][i][j-1]);
}
}
}
