#include "dungeons.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
int S[1000000];
int P[1000000];
int W[1000000];
int L[1000000];
pair<int,lld> STL[1000000][32];
lld NW[1000000];
int N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N=n;
rep(i,0,n){
S[i]=s[i];
P[i]=p[i];
W[i]=w[i];
L[i]=l[i];
}
NW[n]=0;
for(int i=n-1;i>-1;i--){
NW[i]=NW[W[i]]+S[i];
}
rep(i,0,n){
STL[i][0]={L[i],P[i]};
}
for(int j=1;j<30;j++){
rep(i,0,n){
STL[i][j]={STL[STL[i][j-1].first][j-1].first,STL[STL[i][j-1].first][j-1].second+STL[i][j-1].second};
}
}
}
#define DEBUG 0
long long simulate(int x, int z) {
if(DEBUG){
//cout<<x<<" "<<z<<endl;
if(x==N)return z;
if(z<S[x])return simulate(L[x],z+P[x]);
return simulate(W[x],z+S[x]);
}else{
//if(x!=0 || z!=8)cerr<<x<<" "<<z<<endl;
for(int j=29;j>-1;j--){
if(STL[x][j].second+z<S[x]){
z+=STL[x][j].second;
x=STL[x][j].first;
return simulate(x,z);
}
}
if(z<S[x]){
return simulate(L[x],z+P[x]);
}else{
return z+NW[x];
}
}
}
