#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=4e5+50,lg=24,lg1=8,inf=1e9;
const ll INF=1e18;
int n;
vector<int>s,p,w,l;
int par[lg1+1][lg+1][N];
ll Sum[lg1+1][lg+1][N],Max[lg1+1][lg+1][N];
void init(int n,vector<int>s,vector<int>p,vector<int>w,vector<int>l){
::n=n;::s=s;::p=p;::w=w;::l=l;
for(int k=0,e=1;k<=lg1;k++,e*=8){
for(int i=0;i<n;i++){
if(s[i]<e){
par[k][0][i]=w[i];
Sum[k][0][i]=s[i];
Max[k][0][i]=-INF;
}
else{
par[k][0][i]=l[i];
Sum[k][0][i]=p[i];
Max[k][0][i]=-s[i];
}
}
par[k][0][n]=n;
Max[k][0][n]=-INF;
for(int j=0;j<lg;j++)for(int i=0;i<=n;i++){
par[k][j+1][i]=par[k][j][par[k][j][i]];
Sum[k][j+1][i]=Sum[k][j][i]+Sum[k][j][par[k][j][i]];
Max[k][j+1][i]=max(Max[k][j][i],Sum[k][j][i]+Max[k][j][par[k][j][i]]);
}
}
}
ll simulate(int x,int z1){
ll z=z1;
for(int k=0,e=1;k<=lg1;k++,e*=8){
ll e1=e*8;
if(k==lg1)e1=INF;
while(e<=z&&z<e1&&x<n){
for(int j=lg;j>=0;j--){
if(par[k][j][x]<n&&z+Sum[k][j][x]<e1&&z+Max[k][j][x]<0){
z+=Sum[k][j][x];
x=par[k][j][x];
}
}
if(z>=s[x]){
z+=s[x];
x=w[x];
}
else{
z+=p[x];
x=l[x];
}
}
}
return z;
}
