#include "dungeons.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "Ofast")
#define ll long long
#define se second
#define fi first
#define pb push_back
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<pii,pii> ipii;
const int MAXN = 5e4+10;
const int MAXA = 5e4+10;
const int SQRT = 300;
const ll INF = 1e9;
const int MOD = 998244353;
const int LOG = 40;
ll n, s[MAXN], p[MAXN], w[MAXN], l[MAXN];
pii bin[MAXN][LOG+5][5];
ll up[MAXN];
vector<ll> vec;
void build(int k){
for(int j=0; j<LOG; j++) bin[n+1][j][k] = {n+1, 0};
for(int i=1; i<=n; i++){
if(s[i] >= vec[k]) bin[i][0][k] = {l[i], p[i]};
else bin[i][0][k] = {w[i], s[i]};
}
for(int j=1; j<LOG; j++){
for(int i=1; i<=n; i++){
ll nx = bin[i][j-1][k].fi, wei = bin[i][j-1][k].se;
bin[i][j][k] = {bin[nx][j-1][k].fi, wei + bin[nx][j-1][k].se};
}
}
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L) {
n = N;
set<ll> se;
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;
se.insert(s[i]);
}
up[n+1] = 0;
for(int i=n; i>=1; i--){
up[i] = up[w[i]]+s[i];
}
for(auto in : se) vec.pb(in);
for(int k=0; k<vec.size(); k++) build(k);
return;
}
long long simulate(int x, int z) {
ll idx = x+1, pow = z, ty = -1;
for(int i=0; i<vec.size(); i++){
if(pow < vec[i]){
ty = i;
break; // yg blm dicapai
}
}
if(ty == -1){
return pow + up[idx];
}
// cout << ty << " ty\n";
for(int k=ty; k<vec.size(); k++){
if(pow >= vec[k]) continue;
for(int i=LOG-1; i>=0; i--){
if(bin[idx][i][k].fi == n+1 || pow+bin[idx][i][k].se >= vec[k]) ;
else {
pow += bin[idx][i][k].se;
idx = bin[idx][i][k].fi;
}
}
pow += bin[idx][0][k].se;
idx = bin[idx][0][k].fi;
if(idx == n+1) return pow;
}
pow += up[idx];
return pow;
}
