#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
vector<int> s, p, w, l;
vector<vector<vector<vector<ll>>>> g;
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l){
::n = n;
::s = s;
::s.push_back(0);
::p = p;
::p.push_back(0);
::w = w;
::w.push_back(n);
::l = l;
::l.push_back(n);
g.resize(n+1, vector<vector<vector<ll>>>(25, vector<vector<ll>>(30, vector<ll>(3))));
for (int k=0; k<25; k++){
for (int i=0; i<n; i++){
if (s[i] <= (1<<k)) g[i][k][0] = {w[i], s[i], (ll)pow(10, 9)};
else g[i][k][0] = {l[i], p[i], s[i]};
}
g[n][k][0] = {n, 0, (ll)pow(10, 9)};
for (int j=1; j<30; j++){
for (int i=0; i<n+1; i++) g[i][k][j] = {g[g[i][k][j-1][0]][k][j-1][0], g[i][k][j-1][1]+g[g[i][k][j-1][0]][k][j-1][1], min(g[i][k][j-1][2], g[g[i][k][j-1][0]][k][j-1][2]-g[i][k][j-1][1])};
}
}
}
ll simulate(int x, int z2){
ll z = z2;
while (x != n){
//cout << x << " " << z << endl;
int k = floor(log2(z));
for (int j=29; j>=0; j--){
if (z + g[x][k][j][1] < (1<<(k+1)) && z < g[x][k][j][2]){
z += g[x][k][j][1];
x = g[x][k][j][0];
}
}
if (z >= s[x]){
z += s[x];
x = w[x];
}
else {
z += p[x];
x = l[x];
}
}
return z;
}
