#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pairll;
#define N 100007
#define fr first
#define sc second
ll n,s[4*N],p[4*N],w[4*N],l[4*N],k[4*N],mx[4*N];
struct D{
ll mxs,mns,dp,ds,pw,pl;
}d[4*N][30];
void init(int _n, vector<int> _s, vector<int> _p, vector<int> _w, vector<int> _l) {
n=_n+1;
for(int i=1;i<n;i++){
s[i]=_s[i-1];
p[i]=_p[i-1];
w[i]=_w[i-1]+1;
l[i]=_l[i-1]+1;
d[i][0]={s[i]+s[i],s[i]+p[i],p[i],s[i],w[i],l[i]};
}
for(int i=1;i<=27;i++){
for(int j=1;j<=n-1;j++){
d[j][i].mxs=max(d[d[j][i-1].pw][i-1].mxs,d[j][i-1].mxs+d[d[j][i-1].pw][i-1].ds);
d[j][i].mns=min(d[d[j][i-1].pl][i-1].mns,d[j][i-1].mns+d[d[j][i-1].pl][i-1].dp);
d[j][i].dp=d[j][i-1].dp+d[d[j][i-1].pl][i-1].dp;
d[j][i].ds=d[j][i-1].ds+d[d[j][i-1].pw][i-1].ds;
d[j][i].pw=d[d[j][i-1].pw][i-1].pw;
d[j][i].pl=d[d[j][i-1].pl][i-1].pl;
}
}
for(int i=n-1;i>=1;i--){
k[i]=k[w[i]]+s[i];
mx[i]=max(mx[w[i]],s[i]);
}
return ;
}
pairll S0(ll x,ll y){
for(int i=27;i>=0;i--){
if(d[x][i].mns>y+d[x][i].dp){
y+=d[x][i].dp;
x=d[x][i].pl;
}
}
return make_pair(x,y);
}
pairll S1(ll x,ll y){
for(int i=27;i>=0;i--){
if(d[x][i].mxs<=y+d[x][i].ds){
y+=d[x][i].ds;
x=d[x][i].pw;
}
}
return make_pair(x,y);
}
long long simulate(int _x, int _z) {
ll x=_x;
ll z=_z;
x++;
ll tp=0;
if(s[x]<=z)tp=1;
while(x!=0){
if(tp==0){
pairll m1=S0(x,z);
x=m1.fr;
z=m1.sc;
}else{
pairll m1=S1(x,z);
x=m1.fr;
z=m1.sc;
}
tp^=1;
}
return z;
}
