#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define REP(i,n) for(int i = 0; i < n; i ++)
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define vi vector<int>
#define pb push_back
#define pii pair<int,int>
#define F first
#define S second
const int MX = 50005;
const int LG = 25;
const int STA = 25;
int n,s[MX],p[MX],w[MX],l[MX];
pii win[MX][LG+5];
int wincond[MX][LG+1];
pii lose[STA+1][MX][LG+1];
int losecond[STA+1][MX][LG+1];
vi st;
void init(signed n0, vector<signed> s0, vector<signed> p0, vector<signed> w0, vector<signed> l0) {
n = n0;
REP(i,n){
s[i] = s0[i];
p[i] = p0[i];
w[i] = w0[i];
l[i] = l0[i];
}
st.pb(2);
FOR(i,1,STA) st.pb(2*st.back());
w[n] = n;
l[n] = n;
s[n] = 0;
p[n] = 0;
REP(i,n+1){
win[i][0] = {w[i],s[i]};
wincond[i][0] = s[w[i]]-s[i];
}
FOR(j,1,LG+1){
REP(i,n+1){
win[i][j] = {win[win[i][j-1].F][j-1].F,win[win[i][j-1].F][j-1].S+win[i][j-1].S};
wincond[i][j] = max(wincond[i][j-1],wincond[win[i][j-1].F][j-1]-win[i][j-1].S);
}
}
REP(stage,STA+1){
REP(i,n){
if(stage and s[i] <= st[stage-1]){
l[i] = w[i];
p[i] = s[i];
s[i] = (int)1e16;
}
}
REP(i,n+1){
lose[stage][i][0] = {l[i],p[i]};
losecond[stage][i][0] = s[l[i]]-p[i];
// int j = 0;
// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
}
FOR(j,1,LG+1){
REP(i,n+1){
lose[stage][i][j] = {lose[stage][lose[stage][i][j-1].F][j-1].F,lose[stage][lose[stage][i][j-1].F][j-1].S+lose[stage][i][j-1].S};
losecond[stage][i][j] = min(losecond[stage][i][j-1],losecond[stage][lose[stage][i][j-1].F][j-1]-lose[stage][i][j-1].S);
// cout << stage << " " << i << " " << j << " " << losecond[stage][i][j] << " " << lose[stage][i][j].F << " " << lose[stage][i][j].S << "\n";
}
}
REP(i,n){
s[i] = s0[i];
p[i] = p0[i];
w[i] = w0[i];
l[i] = l0[i];
}
}
}
int simulate(signed x, signed z) {
int ind = x;
int ans = z;
int stage = 0;
while(ind != n){
// cout << ind << " " << ans << "\n";
if(s[ind] > ans){
while(stage < STA and st[stage] <= ans) stage++;
for(int j = LG; j >= 0; j --){
if(losecond[stage][ind][j] > ans){
ans += lose[stage][ind][j].S;
ind = lose[stage][ind][j].F;
}
}
if(s[ind] > ans){
ans += p[ind];
ind = l[ind];
}
}
else{
for(int j = LG; j >= 0; j --){
if(wincond[ind][j] <= ans){
ans += win[ind][j].S;
ind = win[ind][j].F;
}
}
ans += s[ind];
ind = w[ind];
}
}
return ans;
}
