#include "dungeons.h"
#include <bits/stdc++.h>
#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,l;
vector<int> ss;
vector<vector<vector<int>>> nxt;
/*vector<vector<vector<int>>> nxt;
vector<vector<vector<int>>> nxp;*/
vector<long long> tw;
const int LOG=24;
const int MAXS=1e7+1;
int sn;
long long pth(int x){
if(x==N) return 0;
if(tw[x]>=0) return tw[x];
tw[x]=pth(w[x])+(long long)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+1);
l.resize(N+1);
l[N]=N;
w[N]=N;
for (int i = 0; i < n; i++)
{
s[i]=S[i];
p[i]=P[i];
w[i]=W[i];
l[i]=L[i];
}
ss.push_back(0);
int u=1;
ss.push_back(u);
while(u<MAXS){
u*=2;
ss.push_back(u);
}
sn=sz(ss);
nxt.resize(N+1,vector<vector<int>>(LOG,vector<int>(sn*3,0)));
for (int i = 0; i < n; i++){
for (int j = 0; j < sz(ss); j++)
{
if(s[i]<=ss[j]){
nxt[i][0][j]=s[i];
nxt[i][0][j+sn]=w[i];
nxt[i][0][j+sn*2]=1e8;
}else{
nxt[i][0][j]=p[i];
nxt[i][0][j+sn]=l[i];
nxt[i][0][j+sn*2]=s[i];
}
}
}
for (int j = 1; j < LOG; j++)
{
for (int i = 0; i < N; i++)
{
for (int k = 0; k < sz(ss); k++){
nxt[i][j][k+sn]=nxt[nxt[i][j-1][k+sn]][j-1][k+sn];
nxt[i][j][k]=nxt[i][j-1][k]+nxt[nxt[i][j-1][k+sn]][j-1][k];
nxt[i][j][k+2*sn]=min(nxt[i][j-1][k+2*sn],nxt[nxt[i][j-1][k+sn]][j-1][k+2*sn]-nxt[i][j-1][k]);
}
}
}
return;
}
long long simulate(signed x, signed z) {
int cs=z;
int u=x;
for (int i = 0; i < sz(ss); i++)
{
if(ss[i+1]<=cs) continue;
for (int j = LOG-1; j >= 0; j--)
{
if(nxt[u][j][i+sn]==N||nxt[u][j][i+2*sn]<=cs) continue;
cs+=nxt[u][j][i];
u=nxt[u][j][i+sn];
}
if(nxt[u][0][i+sn]==N){
if(s[u]>cs) cs+=p[u];
else cs+=s[u];
return cs;
}else{
if(s[u]>cs) {
cs+=p[u];
u=l[u];
}
else {
cs+=s[u];
u=w[u];
}
}
if(u==N) return cs;
}
return (long long)cs+pth(u);
}
