#include "dungeons.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const int K = 43;
const ll inf = 1e18;
int n;
vector<int> S, P, W, L;
int* jump[K];
ll* sum[K];
ll* dp[K];
int msb(ll x){
return 63-__builtin_clzll(x);
}
pair<int, ll> binlift(int nd, ll s){
if(nd == n) return {nd, s};
if(s <= dp[msb(s)][nd]) return binlift(jump[msb(s)][nd], s+sum[msb(s)][nd]);
else if(s >= S[nd]) return binlift(W[nd], s+S[nd]);
else return binlift(L[nd], s+P[nd]);
}
void init(int _n, vector<int> _S, vector<int> _P, vector<int> _W, vector<int> _L){
n = _n, S = _S, P = _P, W = _W, L = _L;
S.pb(0);
P.pb(0);
for(int k = 0; k < K; k++){
jump[k] = new int[n+1];
sum[k] = new ll[n+1];
dp[k] = new ll[n+1];
fill(jump[k], jump[k]+n+1, n);
fill(sum[k], sum[k]+n+1, 0);
fill(dp[k], dp[k]+n+1, 0);
}
vector<int> state(n+1, 0);
vector<int> jumpd(n+1, 0);
function<void(int, int)> create_pointers = [&](int k, int nd){
int p;
ll sm, _dp;
if(S[nd] <= (1LL<<k)){
p = W[nd];
sm = S[nd];
_dp = inf;
}
else{
p = L[nd];
sm = P[nd];
_dp = S[nd]-1;
}
state[nd] = 1;
if(state[p] != 2){
if(!state[p]) create_pointers(k, p);
else{
jump[k][nd] = p;
sum[k][nd] = sm;
dp[k][nd] = _dp;
jumpd[nd] = 1;
state[nd] = 2;
return;
}
}
if(jumpd[p] == jumpd[jump[k][p]]){
jump[k][nd] = jump[k][jump[k][p]];
jumpd[nd] = jumpd[p]+jumpd[jump[k][p]]+1;
sum[k][nd] = sum[k][p]+sum[k][jump[k][p]]+sm;
dp[k][nd] = min(_dp, min(dp[k][p]-sm, dp[k][jump[k][p]]-sm-sum[k][p]));
}
else{
jump[k][nd] = p;
sum[k][nd] = sm;
dp[k][nd] = _dp;
jumpd[nd] = 1;
}
state[nd] = 2;
};
for(int k = 0; k < K; k++){
state.assign(n+1, 0);
jumpd.assign(n+1, 0);
state[n] = 2;
create_pointers(k, 0);
}
}
ll simulate(int x, int z){
return binlift(x, z).sc;
}
