#include "dungeons.h"
#include <bits/stdc++.h>
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int N;
vector<int> s,p,w;
vector<vector<int>> nxt,l;
vector<int> tw;
const int LOG=22;
int pth(int x){
if(x==N) return 0;
if(tw[x]>=0) return tw[x];
tw[x]=pth(w[x])+s[x];
return tw[x];
}
void init(signed n, std::vector<signed> S, std::vector<signed> P, std::vector<signed> W, std::vector<signed> L) {
N=n;
s.resize(N);
tw.resize(N,-1);
p.resize(N);
w.resize(N);
l.resize(N+1,vector<int>(LOG,0));
nxt.resize(N,vector<int>(LOG,0));
l[n][0]=0;
for (int i = 0; i < n; i++)
{
s[i]=S[i];
p[i]=P[i];
w[i]=W[i];
l[i][0]=L[i];
if(l[i][0]==N) nxt[i][0]=-1;
else nxt[i][0]+=p[i];
}
for (int i = 0; i < N; i++)
{
for (int j = 1; j < LOG; j++)
{
l[i][j]=l[l[i][j-1]][j-1];
if(nxt[i][j-1]==-1) nxt[i][j]=-1;
else if(nxt[l[i][j-1]][j-1]==-1) nxt[i][j]=-1;
else nxt[i][j]=nxt[i][j-1]+nxt[l[i][j-1]][j-1];
}
}
for (int i = 0; i < N; i++) pth(i);
return;
}
long long simulate(signed x, signed z) {
int cs=z;
int u=x;
if(cs>=s[0]) return cs+pth(x);
for (int j = LOG-1; j >= 0; j--)
{
if(nxt[u][j]==-1||nxt[u][j]+cs>=s[0]) continue;
cs+=nxt[u][j];
u=l[u][j];
}
cs+=nxt[u][0];
u=l[u][0];
return cs+pth(u);
}
