#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lg2 = 8;
const int lg = 24;
const int inf = 1e9;
const int MAXN = 400010;
int N;
int sum[lg2][MAXN][lg];
int mn[lg2][MAXN][lg];
int pos[lg2][MAXN][lg];
ll dist[MAXN];
int S[MAXN], W[MAXN];
void init(int _n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
N = _n;
for (int i=0; i<N; i++) {
S[i] = s[i];
W[i] = w[i];
}
for (int i=0; i<lg2; i++) {
for (int j=0; j<N; j++) {
if (s[j] < (1<<(3*i))) {
mn[i][j][0] = inf;
sum[i][j][0] = s[j];
pos[i][j][0] = w[j];
}
else {
mn[i][j][0] = s[j];
sum[i][j][0] = p[j];
pos[i][j][0] = l[j];
}
}
mn[i][N][0] = inf;
sum[i][N][0] = 0;
pos[i][N][0] = N;
for (int lv=1; lv<lg; lv++) {
for (int j=0; j<=N; j++) {
int nxt = pos[i][j][lv-1];
mn[i][j][lv] = mn[i][j][lv-1];
if (mn[i][nxt][lv-1] != inf) {
if (mn[i][nxt][lv-1] <= sum[i][j][lv-1])
mn[i][j][lv] = 0;
else mn[i][j][lv] = min(mn[i][j][lv], mn[i][nxt][lv-1] - (int)sum[i][j][lv-1]);
}
sum[i][j][lv] = min(inf, sum[i][j][lv-1] + sum[i][nxt][lv-1]);
pos[i][j][lv] = pos[i][nxt][lv-1];
}
}
}
dist[N] = 0;
for (int i=N-1; i>=0; i--) {
dist[i] = dist[w[i]] + (ll)s[i];
}
return;
}
ll simulate(int x, int z) {
ll Z = z;
for (int i=0; i<lg2; i++) {
for (int rep=0; rep<7; rep++) {
if (Z >= (1<<(3*i+3))) break;
for (int lv=lg-1; lv>=0; lv--) {
if (mn[i][x][lv] > Z && sum[i][x][lv] < inf) {
Z += (ll)sum[i][x][lv];
x = pos[i][x][lv];
}
}
if (x == N) return Z;
Z += (ll)S[x];
x = W[x];
if (x == N) return Z;
}
}
return Z + dist[x];
}
