#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=28;
ll inf=1e18;
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];
ll par[N][lg+1][7],sum[N][lg+1][7];
vector<ll>Vals;
//int IND(int x){for(int i=0;i<Vals.size();i++) if(Vals[i]==x) return i;}
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]);Vals.pb(s[i]);}
sort(Vals.begin(),Vals.end());
int mmm=unique(Vals.begin(),Vals.end())-Vals.begin();
Vals.resize(mmm);
//for(auto i:Vals) printf("%lld ",i);printf("\n");
for(int i=0;i<n;i++){
/*par[i][0]=w[i];
par1[i][0]=l[i];
sum[i][0]=p[i];*/
for(int j=0;j<=Vals.size();j++){
ll R=inf;if(j!=Vals.size()) R=Vals[j];
if(s[i]<R){
par[i][0][j]=w[i];
sum[i][0][j]=s[i];
}
else{
par[i][0][j]=l[i];
sum[i][0][j]=p[i];
}
}
}
for(int i=0;i<=lg;i++) for(int j=0;j<=5;j++) par[n][i][j]=n;
for(int j=1;j<=lg;j++){
for(int i=0;i<n;i++){
for(int k=0;k<=Vals.size();k++){
par[i][j][k]=par[par[i][j-1][k]][j-1][k];
sum[i][j][k]=sum[i][j-1][k]+sum[par[i][j-1][k]][j-1][k];
}
}
}
//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];
}*/
for(int k=0;k<=Vals.size();k++){
ll R=inf;if(k!=Vals.size()) R=Vals[k];
//printf("|%i %lld\n",k,R);
for(int i=lg;i>=0;i--){
//printf("%i %i %i: %lld %lld %lld %lld\n",x,i,k,par[x][i][k],sum[x][i][k],Z+sum[x][i][k],R);
if(par[x][i][k]<n && Z+sum[x][i][k]<R){
Z+=sum[x][i][k];
x=par[x][i][k];
//printf("da\n");
}
}
//printf("*%i %lld\n",x,Z);
if(x<n && Z<R){
if(Z>=s[x]){
Z+=s[x];
x=w[x];
}
else{
Z+=p[x];
x=l[x];
}
}
//printf("*%i %lld\n",x,Z);
}
return Z;
}
