#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=4e5+50,lg=30;
ll n,s[N],p[N],w[N],l[N],maks;
ll par[N][lg+1],par1[N][lg+1],sum[N][lg+1],sum1[N][lg+1];
void init(int n1, std::vector<int> s1, std::vector<int> p1, std::vector<int> w1, std::vector<int> l1) {
n=n1;
for(int i=0;i<n;i++){s[i]=s1[i],p[i]=p1[i],w[i]=w1[i],l[i]=l1[i];maks=max(maks,s[i]);}
for(int i=0;i<n;i++){
par[i][0]=w[i];
par1[i][0]=l[i];
sum[i][0]=p[i];
}
for(int i=0;i<=lg;i++) par[n][i]=par1[n][i]=n;
for(int j=1;j<=lg;j++) for(int i=0;i<n;i++){par[i][j]=par[par[i][j-1]][j-1];par1[i][j]=par1[par1[i][j-1]][j-1];sum[i][j]=sum[i][j-1]+sum[par1[i][j-1]][j-1];}
//for(int i=0;i<=n;i++) for(int j=0;j<=5;j++) printf("%i %i: %lld %lld %lld\n",i,j,par[i][j],par1[i][j],sum[i][j]);
return;
}
long long simulate(int x, int z) {
ll Z=z;
while(x<n && Z<maks){
if(Z>=s[x]){
Z+=s[x];
x=w[x];
}
else{
Z+=p[x];
x=l[x];
}
//printf("*%i %lld\n",x,Z);
}
/*for(int i=lg;i>=0;i--){
if(Z+sum[x][i]<s[0] && par1[x][i]<n){
Z+=sum[x][i];
x=par1[x][i];
}
}
if(Z<s[x]){
Z+=p[x];
x=l[x];
}*/
for(int i=lg;i>=0;i--){
if(par[x][i]<n){
ll val=(ll)1<<i;
Z+=sum[x][i];
x=par[x][i];
}
}
if(x<n){
Z+=s[x];
x=w[x];
}
return Z;
}
