#include<bits/stdc++.h>
#include "dungeons.h"
using namespace std;
const int MAX_N = 50009;
int msh[MAX_N][26][26];
long long a, b, c, d, e, i, j, k, ii, jj, zx, xc, S[MAX_N], P[MAX_N], W[MAX_N], L[MAX_N], dis[MAX_N][26][26], mn[MAX_N][26][26], z;
void init(int Nn, vector<int> Ss, vector<int> Pp, vector<int> Ww, vector<int> Ll) {
a = Nn;
for (i = 0; i < a; i++) {
S[i + 1] = Ss[i];
P[i + 1] = Pp[i];
W[i + 1] = Ww[i] + 1;
L[i + 1] = Ll[i] + 1;
}
for (i = 1; i <= a; i++) {
for (k = 0; k <= 24; k++) {
if (S[i] < (1 << k)) {
msh[i][0][k] = W[i];
dis[i][0][k] = S[i];
mn[i][0][k] = LLONG_MAX;
} else {
msh[i][0][k] = L[i];
dis[i][0][k] = P[i];
mn[i][0][k] = S[i];
}
}
}
for (j = 1; j <= 24; j++) {
for (i = 1; i <= a; i++) {
for (k = 0; k <= 24; k++) {
msh[i][j][k] = msh[msh[i][j - 1][k]][j - 1][k];
dis[i][j][k] = dis[i][j - 1][k] + dis[msh[i][j - 1][k]][j - 1][k];
mn[i][j][k] = min(mn[i][j - 1][k], mn[msh[i][j - 1][k]][j - 1][k] - dis[i][j - 1][k]);
}
}
}
}
long long simulate(int Xx, int Zz) {
c = Xx + 1;
z = Zz;
while (c != a + 1) {
for (k = 24; k >= 0; k--) if (z >= (1 << k)) break;
for (j = 24; j >= 0; j--) {
if (msh[c][j][k] == 0) continue;
if (mn[c][j][k] > z) {
z += dis[c][j][k];
c = msh[c][j][k];
}
}
if (c == a + 1) break;
if (z >= S[c]) {
z += S[c];
c = W[c];
} else {
z += P[c];
c = L[c];
}
}
return z;
}
