#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][lg][MAXN];
int mn[lg2][lg][MAXN];
int pos[lg2][lg][MAXN];
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][0][j] = inf;
sum[i][0][j] = s[j];
pos[i][0][j] = w[j];
}
else {
mn[i][0][j] = s[j];
sum[i][0][j] = p[j];
pos[i][0][j] = l[j];
}
}
mn[i][0][N] = inf;
sum[i][0][N] = 0;
pos[i][0][N] = N;
for (int lv=1; lv<lg; lv++) {
for (int j=0; j<=N; j++) {
int nxt = pos[i][lv-1][j];
mn[i][lv][j] = mn[i][lv-1][j];
if (mn[i][lv-1][nxt] != inf) {
if (mn[i][lv-1][nxt] <= sum[i][lv-1][j])
mn[i][lv][j] = 0;
else mn[i][lv][j] = min(mn[i][lv][j], mn[i][lv-1][nxt] - (int)sum[i][lv-1][j]);
}
sum[i][lv][j] = min(inf, sum[i][lv-1][j] + sum[i][lv-1][nxt]);
pos[i][lv][j] = pos[i][lv-1][nxt];
}
}
}
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][lv][x] > Z && sum[i][lv][x] < inf) {
Z += (ll)sum[i][lv][x];
x = pos[i][lv][x];
}
}
if (x == N) return Z;
if (Z >= (1<<(3*i+3))) break;
Z += (ll)S[x];
x = W[x];
if (x == N) return Z;
}
}
return Z + dist[x];
}
