#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef tuple<ll,ll,ll> PP;
typedef vector<PP> vpp;
typedef vector<vpp> vvpp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define all(a) a.begin(),a.end()
#define dupli(a) {sort(all(a));a.erase(unique(all(a)),a.end());}
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define fi first
#define se second
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
const ll inf=1001001001001001001;
ll n;
vi s,p,w,l;
vector<vvp> table;
vvi nex;
vi al;
P f(P a,P b){
return P(b.fi,a.se+b.se);
}
void init(int n_, vector<int> s_, vector<int> p_, vector<int> w_, vector<int> l_){
n=n_+1;
for(ll x:s_)s.pb(x);
for(ll x:p_)p.pb(x);
for(ll x:w_)w.pb(x);
for(ll x:l_)l.pb(x);
s.pb(0);p.pb(0);w.pb(n-1);l.pb(n-1);
al=s;dupli(al);
table=vector<vvp>(al.size(),vvp(20,vp(n)));
rep(t,al.size()){
rep(i,n){
if(al[t]>=s[i])table[t][0][i]=P(w[i],s[i]);
else table[t][0][i]=P(l[i],p[i]);
}
rep(i,19)rep(j,n)table[t][i+1][j]=f(table[t][i][j],table[t][i][table[t][i][j].fi]);
}
return;
}
long long simulate(int x_, int z_) {
ll i=x_,cur=z_;
/*
while(i<n-1){
if(cur>=s[i]){
cur+=s[i];
i=w[i];
}
else{
cur+=p[i];
i=l[i];
}
}
*/
while(i<n-1){
/*
if(cur<s[i]){
cur+=p[i];i=l[i];
}
else{
PP tmp(i,0,0);
for(ll j=19;j>=0;j--){
auto ntmp=f(tmp,table[j][get<0>(tmp)]);
if(get<1>(ntmp)<=cur){
tmp=ntmp;
}
}
i=get<0>(tmp);cur+=get<2>(tmp);
}
*/
ll t=lb(al,cur+1)-1,mx=inf;
if(t!=al.size()-1)mx=al[t+1];
P tmp(i,cur);
for(ll j=19;j>=0;j--){
auto ntmp=f(tmp,table[t][j][tmp.fi]);
if(ntmp.se<mx)tmp=ntmp;
}
tmp=f(tmp,table[t][0][tmp.fi]);
i=tmp.fi;cur=tmp.se;
}
return cur;
}
