#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;
vector<vector<int>> nxtW,mxW,w,l,nxtL,mnL;
int avg=0;
const int LOG=24;
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+1);
p.resize(N);
w.resize(N+1,vector<int>(LOG,N));
l.resize(N+1,vector<int>(LOG,N));
nxtW.resize(N+1,vector<int>(LOG,0));
nxtL.resize(N+1,vector<int>(LOG,0));
mxW.resize(N+1,vector<int>(LOG,0));
mnL.resize(N+1,vector<int>(LOG,0));
w[N][0]=N;
s[N]=0;
avg=0;
for (int i = 0; i < n; i++)
{
s[i]=S[i];
p[i]=P[i];
w[i][0]=W[i];
l[i][0]=L[i];
nxtW[i][0]=s[i];
mxW[i][0]=s[i];
mnL[i][0]=s[i];
nxtL[i][0]=p[i];
avg+=s[i];
}
avg/=N;
for (int j = 1; j < LOG; j++)
{
for (int i = 0; i < N; i++)
{
w[N][j]=N;
l[N][j]=N;
w[i][j]=w[w[i][j-1]][j-1];
l[i][j]=l[l[i][j-1]][j-1];
nxtW[i][j]=nxtW[i][j-1]+nxtW[w[i][j-1]][j-1];
nxtL[i][j]=nxtL[i][j-1]+nxtL[l[i][j-1]][j-1];
mxW[i][j]=max(mxW[i][j-1],mxW[w[i][j-1]][j-1]-nxtW[i][j-1]);
mnL[i][j]=min(mnL[i][j-1],mnL[l[i][j-1]][j-1]-nxtL[i][j-1]);
}
}
return;
}
long long simulate(signed x, signed z) {
int cs=z;
int u=x;
int jc=0;
while(u!=N){
if(s[u]<=cs){
if(s[u]>cs) {
cs+=p[u];
u=l[u][0];
continue;
}
int v=u;
for (int j = LOG-1; j >= 0; j--)
{
if(mxW[v][j]>cs) continue;
cs+=nxtW[v][j];
v=w[v][j];
if(v==N) return cs;
}
cs+=p[v];
u=l[v][0];
}else{
jc++;
if(s[u]<=cs) {
cs+=s[u];
u=w[u][0];
continue;
}
int v=u;
for (int j = LOG-1; j >= 0; j--)
{
if(mnL[v][j]<=cs) continue;
cs+=nxtL[v][j];
v=l[v][j];
if(v==N) return cs;
}
cs+=s[v];
u=w[v][0];
}
assert(jc<=5);
}
return cs;
}
