#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#include "dungeons.h"
ll n;
ll s[50005],p[50005],w[50005],l[50005];
ll jump[50005][41][41],sumi[50005][41][41],mini[50005][41][41];
void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
// may need to expand to 41, 1e18, ll
n = N;
for(ll i=1;i<=n;i++){
s[i] = S[i-1];
p[i] = P[i-1];
w[i] = W[i-1]+1;
l[i] = L[i-1]+1;
}
for(ll k=0;k<=40;k++){
jump[n+1][0][k] = n+1;
for(ll i=1;i<=n;i++){
if(s[i]<(1LL<<k)){
jump[i][0][k] = w[i];
sumi[i][0][k] = s[i];
mini[i][0][k] = 1e18;
}
else if(s[i]>=(1LL<<(k+1LL))){
jump[i][0][k] = l[i];
sumi[i][0][k] = p[i];
mini[i][0][k] = 1e18;
}
else{
jump[i][0][k] = l[i];
sumi[i][0][k] = p[i];
mini[i][0][k] = s[i];
}
}
}
for(ll k=0;k<=40;k++){
for(ll j=1;j<=40;j++){
for(ll i=1;i<=n;i++){
jump[i][j][k] = jump[jump[i][j-1][k]][j-1][k];
sumi[i][j][k] = sumi[i][j-1][k]+sumi[jump[i][j-1][k]][j-1][k];
mini[i][j][k] = min(mini[i][j-1][k],mini[jump[i][j-1][k]][j][k]-sumi[i][j-1][k]);
}
}
}
}
ll simulate(int x, int z){
x++;
for(ll k=0;k<=40;k++){
if(z<(1LL<<(k+1LL))){
for(ll j=40;j>=0;j--){
if(z+sumi[x][j][k]<(1LL<<(k+1LL)) and z<mini[x][j][k] and jump[x][j][k]!=n+1){
z += sumi[x][j][k];
x = jump[x][j][k];
}
}
if(z>=s[x]){
z += s[x];
x = w[x];
}
else{
z += p[x];
x = l[x];
}
if(x==n+1){
break;
}
}
}
return z;
}
