#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int LOG1 = 9; // 8^i를 기준
const int LOG2 = 25;
const long long INF = 1e9;
int nxt[400010][LOG1][LOG2];
ll sum[400010][LOG1][LOG2];
ll lmt[400010][LOG1][LOG2];
ll ex[LOG1];
int N;
vector <int> S, P, W, L;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N=n, S=s, P=p, W=w, L=l;
int i, j, k;
ex[0] = 1;
for (i=1; i<LOG1; i++){
ex[i] = ex[i-1]*8;
}
for (i=0; i<LOG1; i++){
for (j=0; j<n; j++){
if (ex[i] >= S[j]){
if (W[j]==n){
nxt[j][i][0] = -1;
}
else{
nxt[j][i][0] = W[j];
sum[j][i][0] = S[j];
lmt[j][i][0] = INF;
}
}
else{
if (L[j]==n){
nxt[j][i][0] = -1;
}
else{
nxt[j][i][0] = L[j];
sum[j][i][0] = P[j];
lmt[j][i][0] = S[j];
}
}
}
}
for (i=0; i<LOG1; i++){
for (j=1; j<LOG2; j++){
for (k=0; k<n; k++){
if (nxt[k][i][j-1]==-1 || nxt[nxt[k][i][j-1]][i][j-1]==-1){
nxt[k][i][j]=-1;
}
else{
nxt[k][i][j] = nxt[nxt[k][i][j-1]][i][j-1];
sum[k][i][j] = sum[k][i][j-1] + sum[nxt[k][i][j-1]][i][j-1];
lmt[k][i][j] = min(lmt[k][i][j-1], lmt[nxt[k][i][j-1]][i][j-1] - sum[k][i][j-1]);
}
}
}
}
return;
}
long long simulate(int x, int z) {
ll str = z;
int i, lv=0;
while(x!=N){
while (lv+1<LOG1 && str>=ex[lv+1]){
lv++;
}
for (i=LOG2-1; i>=0; i--){
if (nxt[x][lv][i]==-1) continue;
if (str>=lmt[x][lv][i]) continue;
str += sum[x][lv][i];
x = nxt[x][lv][i];
}
if (str>=S[x]){
str += S[x];
x = W[x];
}
else{
str += P[x];
x = L[x];
}
}
return str;
}
