#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 KU = 21, KD = 25;
const ll inf = 1.5e17;
int n;
vector<int> S, P, W, L;
vector<int> ancU[KU];
vector<ll> sumU[KU];
vector<ll> dpU[KU];
vector<int> ancD[KD];
vector<ll> sumD[KD];
vector<ll> dpD[KD];
pair<int, ll> binliftUp(int nd, ll s){
if(nd == n || s < S[nd]) return {nd, s};
for(int i = KU-1; i >= 0; i--){
if(s >= dpU[i][nd]) return binliftUp(ancU[i][nd], s+sumU[i][nd]);
}
return {-1, -1};
}
pair<int, ll> binliftDown(int nd, ll s){
if(nd == n || s >= S[nd]) return {nd, s};
for(int i = KD-1; i >= 0; i--){
if(s <= dpD[i][nd]) return binliftDown(ancD[i][nd], s+sumD[i][nd]);
}
return {-1, -1};
}
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);
fill(ancU, ancU+KU, vector<int>(n+1, n));
fill(sumU, sumU+KU, vector<ll>(n+1, 0));
fill(dpU, dpU+KU, vector<ll>(n+1, 0));
for(int i = 0; i < n; i++){
ancU[0][i] = W[i];
sumU[0][i] = S[i];
dpU[0][i] = S[i];
}
for(int p = 1; p < KU; p++) for(int i = 0; i <= n; i++){
ancU[p][i] = ancU[p-1][ancU[p-1][i]];
sumU[p][i] = sumU[p-1][i]+sumU[p-1][ancU[p-1][i]];
dpU[p][i] = max(dpU[p-1][i], dpU[p-1][ancU[p-1][i]]-sumU[p-1][i]);
}
fill(ancD, ancD+KD, vector<int>(n+1, n));
fill(sumD, sumD+KD, vector<ll>(n+1, 0));
fill(dpD, dpD+KD, vector<ll>(n+1, inf));
for(int i = 0; i < n; i++){
ancD[0][i] = L[i];
sumD[0][i] = P[i];
dpD[0][i] = S[i]-1;
}
for(int p = 1; p < KD; p++) for(int i = 0; i <= n; i++){
ancD[p][i] = ancD[p-1][ancD[p-1][i]];
sumD[p][i] = sumD[p-1][i]+sumD[p-1][ancD[p-1][i]];
dpD[p][i] = min(dpD[p-1][i], dpD[p-1][ancD[p-1][i]]-sumD[p-1][i]);
}
}
ll simulate(int x, int z){
ll s = z;
while(x != n){
tie(x, s) = binliftUp(x, s);
if(x == n) break;
tie(x, s) = binliftDown(x, s);
}
return s;
}
