#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=4e5+5;
long long sz,S[N],P[N],W[N],L[N],Sum[N][21],nxt[N][21],mx[N][21],d[N];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l){
sz=n;
for(int i=1;i<=n;i++){
S[i]=s[i-1];
P[i]=p[i-1];
W[i]=w[i-1];
L[i]=l[i-1];
W[i]++;
L[i]++;
}
S[n+1]=0;
L[n+1]=W[n+1]=1;
for(int j=0;j<=20;j++){
nxt[n+1][j]=n+1;
mx[n+1][j]=1e18;
Sum[n+1][j]=0;
}
for(int i=1;i<=n;i++){
nxt[i][0]=W[i];
Sum[i][0]=S[i];
mx[i][0]=S[i];
}
for(int j=1;j<=20;j++){
for(int i=1;i<=n+1;i++){
nxt[i][j]=nxt[nxt[i][j-1]][j-1];
Sum[i][j]=Sum[i][j-1]+Sum[nxt[i][j-1]][j-1];
mx[i][j]=max(mx[i][j-1],mx[nxt[i][j-1]][j-1]);
}
}
d[n+1]=0;
for(int i=n;i>=1;i--){
d[i]=1+d[W[i]];
}
return ;
}
long long simulate(int x, int z){
++x;
long long power=z;
while(x!=sz+1){
int cnt=0;
//cout<<" # "<<x<<' '<<power;
for(int j=20;j>=0;j--){
if(mx[x][j]>power || (1<<j)>d[x]) continue ;
cnt+=(1<<j);
power+=Sum[x][j];
x=nxt[x][j];
}
if(x==sz+1) break ;
// cout<<" % "<<x<<' '<<power<<' ';
if(S[x]>power){
power+=S[x];
x=L[x];
}
else{
power+=S[x];
x=W[x];
}
//cout<<" $ "<<x<<' '<<power<<endl;
}
//cout<<endl;
return power;
}
