#include "dungeons.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::vector;
using std::string;
using std::endl;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define all(a) a.begin(), a.end()
#define pb emplace_back
#define mp std::make_pair
constexpr ll inf = (1ll<<60);
struct segment_tree{
ll N;
vi node;
segment_tree(int n){
N = 1;
while(N <= n) N *= 2;
node.resize(2*N,-inf);
}
void update(ll idx, ll val){
idx += N;
node[idx] = val;
idx /= 2;
while(idx){
node[idx] = compare(node[idx*2], node[idx*2+1]);
idx /= 2;
}
}
ll min_right(ll val, ll a, ll now = 1, ll l = 0, ll r = -1){
if(r == -1) r = N;
if(r <= a) return r;
if(val >= node[now]) return r;
if(now >= N) return l;
ll mid = min_right(val, a, now*2, l, (l+r)/2);
if(mid == (l+r)/2) return min_right(val, a, now*2+1, (l+r)/2, r);
return mid;
}
ll compare(ll l, ll r){
return std::max(l,r);
}
};
vii t1_edge, t1_weight;
vi t1_dist, t1_par, t1_next;
ll N;
vi S,P,W,L;
constexpr ll LOG = 25;
std::map<ll,ll> set;
vi rev;
ll min[6][50010][25], sum[6][50010][25], idx[6][50010][25];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n+1;
rep(i,0,n) S.pb(s[i]), P.pb(p[i]), W.pb(w[i]), L.pb(l[i]);
{
t1_edge.resize(N);
t1_weight.resize(N);
t1_dist.resize(N);
t1_par.resize(N);
t1_next.resize(N);
rep(i,0,n){
t1_edge[w[i]].pb(i);
t1_weight[w[i]].pb(s[i]);
t1_par[i] = w[i];
}
vi dist2(N);
segment_tree seg(N+1);
vi v;
std::function<void(ll)> dfs = [&](ll now){
v.pb(now);
t1_next[now] = v[std::max(0ll, N-seg.min_right(s[now]+t1_dist[now], 0))];
seg.update(N-dist2[now], s[now]+t1_dist[now]);
for(auto next: t1_edge[now]){
dist2[next] = dist2[now]+1;
t1_dist[next] = t1_dist[now]+s[next];
dfs(next);
}
seg.update(N-dist2[now], -inf);
v.pop_back();
};
dfs(N-1);
}
{
rep(i,0,n) set[s[i]] = 0;
{
set[-inf] = 0;
ll v = 0;
for(auto &el: set){
el.second = v++;
rev.pb(el.first);
}
}
L.pb(N-1);
P.pb(0);
S.pb(-inf);
rep(t,0,set.size()){
rep(i,0,N){
if(S[i] > rev[t] || i == N-1){
idx[t][i][0] = L[i];
sum[t][i][0] = P[i];
min[t][i][0] = S[i];
}
else{
idx[t][i][0] = W[i];
sum[t][i][0] = S[i];
min[t][i][0] = inf;
}
}
rep(j,1,LOG){
rep(i,0,N){
ll now = idx[t][i][j-1];
ll next = idx[t][now][j-1];
idx[t][i][j] = next;
sum[t][i][j] = sum[t][i][j-1]+sum[t][now][j-1];
min[t][i][j] = std::min(min[t][i][j-1], min[t][now][j-1]-sum[t][i][j-1]);
}
}
}
}
}
long long simulate(int x, int z) {
ll now = x;
ll ans = z;
while(true){
if(now == N-1) break;
if(S[now] > ans){
ll t = std::upper_bound(all(rev), ans)-rev.begin()-1;
per(i,LOG-1,0){
if(min[t][now][i] > ans){
ans += sum[t][now][i];
now = idx[t][now][i];
}
}
}
else{
ans += t1_dist[now]-t1_dist[t1_next[now]];
now = t1_next[now];
}
}
return ans;
}
