#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int LOG = 24;
struct Data{
int pos;
ll sum, need;
};
Data combine(Data a, Data b){
Data c;
c.pos = b.pos;
c.sum = a.sum + b.sum;
c.need = min(a.need, b.need-a.sum);
return c;
}
int n;
vector<int> s, p, w, l;
vector<vector<vector<Data>>> jump;
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_;
jump.assign(LOG, vector<vector<Data>>(LOG, vector<Data>(n+1)));
for(int i = 0; i < LOG; i++){
for(int j = 0; j < n; j++){
if(s[j] <= (1<<i)) jump[i][0][j] = {w[j], s[j], INF};
else jump[i][0][j] = {l[j], p[j], s[j]};
}
jump[i][0][n] = {n, 0, 0};
for(int k = 1; k < LOG; k++){
for(int j = 0; j <= n; j++){
jump[i][k][j] = combine(jump[i][k-1][j], jump[i][k-1][jump[i][k-1][j].pos]);
}
}
}
}
ll simulate(int x, int z) {
ll ans = z;
while(x != n){
if(ans >= s[x]){
ans += s[x];
x = w[x];
continue;
}
int layer;
for(layer = 0; layer <= LOG && ans >= (1<<layer); layer++);
layer--;
Data d{x, ans, INF};
for(int k = LOG-1; k >= 0; k--){
Data d2 = combine(d, jump[layer][k][d.pos]);
if(d2.need > 0) d = d2;
}
ans = d.sum;
x = d.pos;
}
return ans;
}
