#include "dungeons.h"
using namespace std;
#include <vector>
#define LOG 25
#define X first
#define Y second
#define ll long long
int n;
struct dungeon{
ll s,p,w,l,z;
vector<pair<int,ll>> v;
dungeon(){}
dungeon(int _s,int _p,int _w,int _l){
s=_s;p=_p;w=_w;l=_l;
v.resize(LOG);
v[0]={l,p};
}
};
vector<dungeon> v;
void init(int _n, std::vector<int> _s, std::vector<int> _p, std::vector<int> _w, std::vector<int> _l) {
n=_n;
v.resize(n);
for (int i=0;i<n;i++){
v[i]=dungeon(_s[i],_p[i],_w[i],_l[i]);
}
for (int i=n-1;i>=0;i--){
v[i].z=v[i].s;
if (v[i].w!=n){
v[i].z+=v[v[i].w].z;
}
}
for (int j=1;j<LOG;j++){
for (int i=0;i<n;i++){
if (v[i].v[j-1].X==n){
v[i].v[j]=v[i].v[j-1];
}else{
v[i].v[j]={v[v[i].v[j-1].X].v[j-1].X,v[v[i].v[j-1].X].v[j-1].Y+v[i].v[j-1].Y};
}
}
}
}
long long simulate(int x, int s) {
ll z=s;
for (int j=LOG-1;j>=0;j--){
if (z+v[x].v[j].Y>v[0].s){continue;}
z+=v[x].v[j].Y;
x=v[x].v[j].X;
if (x==n){break;}
}
if (z<v[0].s&&x!=n){
z+=v[x].v[0].Y;
x=v[x].v[0].X;
}
if (x!=n){
z+=v[x].z;
}
return z;
}
