#include <bits/stdc++.h>
#include "dungeons.h"
using namespace std;
const int mxN = (int)5e4+5;
const int lg = (int)8;
int lim[mxN][lg][32];
int gget[mxN][lg][32];
int jump[mxN][lg][32];
int N;
vector<int>S; vector<int>P; vector<int>W; vector<int>L;
void init(int n, vector<int>s, vector<int>p, vector<int>w, vector<int>l) {
S = s, P = p, W = w, L = l;
N = n;
for(int j = 0 ; j < lg ; j++) {
for(int i = 0 ; i < n ; i++) {
if(pow(8,j) >= s[i]) {
lim[i][j][0] = INT_MAX;
gget[i][j][0] = s[i];
jump[i][j][0] = w[i];
} else {
lim[i][j][0] = s[i];
gget[i][j][0] = p[i];
jump[i][j][0] = l[i];
}
}
}
for(int k = 1 ; k < 30 ; k++) {
for(int j = 0 ; j < lg ; j++) {
for(int i = 0 ; i < n ; i++) {
lim[i][j][k] = min(lim[i][j][k-1], lim[ jump[i][j][k-1] ][j][k-1] - gget[i][j][k-1]);
gget[i][j][k] = gget[i][j][k-1] + gget[ jump[i][j][k-1] ][j][k-1];
jump[i][j][k] = jump[ jump[i][j][k-1] ][j][k-1];
}
}
}
}
long long simulate(int x, int z) {
long long c = z;
int pw = 0;
while(x != N) {
while(pow(8,(pw+1)) <= c && pw+1 <= 8) {
pw++;
}
for(int j = 30 ; j >= 0 ; j--) {
if(lim[x][pw][j] >= c && jump[x][pw][j] != N) {
c += gget[x][pw][j];
x = jump[x][pw][j];
}
}
if(x != N) {
if(c >= S[x]) {
c += S[x];
x = W[x];
} else {
c += P[x];
x = L[x];
}
}
}
return c;
}
