#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define pb push_back
#define F first
#define pii pair<int,int>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 4e5 + 10 , lg = 29, inf = 1e9+ 10 , S = 15000, mod = 998244353;
int s[maxn] , p[maxn] , w[maxn], l[maxn] , n ;
ll sm[maxn][lg+1] , mn[maxn][lg+1] ;
int par[maxn][lg+1] ,mx , is[maxn][lg+1] ;
void init(int N, std::vector<int> s2, std::vector<int> p2, std::vector<int> w2, std::vector<int> l2) {
n = N ;
rep(i , 0, n-1){
s[i] = s2[i];
mx=max(mx ,s[i]) ;
p[i] = p2[i] ;
l[i] =l2[i];
w[i] = w2[i] ;
}
w[n] = l[n] = n ;
s[n] = p[n] = 0 ;
rep(i ,0 , lg){
par[n][i] = n ;
is[n][i] = 1;
mn[n][i] = 0 ;
}
rep(i ,0 , n-1){
if(s[i] < S){
sm[i][0] = s[i] ;
par[i][0] = w[i] ;
is[i][0] = (w[i]==n);
mn[i][0] = inf ;
}else{
sm[i][0] = p[i] ;
par[i][0] = l[i];
is[i][0] = (l[i] == n) ;
mn[i][0] = s[i] ;
}
}
rep(j , 1 ,lg){
rep(i , 0 ,n-1){
par[i][j] = par[par[i][j-1]][j-1] ;
is[i][j] = is[i][j-1] | is[par[i][j-1]][j-1] ;
sm[i][j] = sm[i][j-1] + sm[par[i][j-1]][j-1] ;
mn[i][j] = min(mn[i][j-1] , mn[par[i][j-1]][j-1] - sm[i][j-1]) ;
}
}
return;
}
int x;
ll z ;
inline void nx(){
if(s[x] <= z){
z += s[x];
x = w[x];
}else{
z += p[x];
x = l[x];
}
}
long long simulate(int X, int Z) {
x = X ;
z = Z ;
while(x!=n && z <= S){
nx();
}
if(x==n)return z;
while(z < mx && x!=n){
per(i , lg ,1){
if(mn[x][i-1] <= z || is[x][i-1]){
continue ;
}
z += sm[x][i-1];
x = par[x][i-1];
}
nx();
}
if(x==n)return z ;
while(x!=n){
nx();
}
return z;
}
