#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 50001;
const int LOG = 26;
vector<long long> win(MAX_N);
vector<vector<vector<long long>>> dist, nxt, mini;
set<long long> temp;
vector<int> s,p,w,l;
int n;
void init(int nn, vector<int> ss, vector<int> pp, vector<int> ww, vector<int> ll) {
ios::sync_with_stdio(false);
cin.tie(0);
s = ss; p = pp; w = ww; l = ll; n = nn;
l.push_back(n); p.push_back(0); s.push_back(0); w.push_back(n);
for (int i = 0; i < n; i++) temp.insert(s[i]);
dist.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size())));
nxt.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size())));
mini.resize(MAX_N, vector<vector<long long>>(LOG, vector<long long>(temp.size())));
auto it = temp.begin();
for (int i = 0; i < (int)(temp.size()); i++, it++){
for (int j = 0; j <= n; j++) {
if (s[j] >= *it) {
dist[j][0][i] = p[j];
nxt[j][0][i] = l[j];
mini[j][0][i] = s[l[j]];
}else {
dist[j][0][i] = s[j];
nxt[j][0][i] = w[j];
mini[j][0][i] = *it;
}
}
}
for (int i = 0; i < (int)(temp.size()); i++){
for (int j = 0; j <= n; j++) {
for (int k = 1; k < LOG; k++) {
dist[j][k][i] = dist[j][k-1][i] + dist[nxt[j][k-1][i]][k-1][i];
nxt[j][k][i] = nxt[nxt[j][k-1][i]][k-1][i];
mini[j][k][i] = min(mini[j][k-1][i], mini[nxt[j][k-1][i]][k-1][i]);
}
}
}
win[n] = 0;
for (int i = n-1; i >= 0; i--) {
win[i] = win[w[i]] + s[i];
}
return;
}
long long simulate(int x, int z) {
long long lim = s[x];
long long st = z;
int pos = x;
if (st >= lim) return st+ win[pos];
for (int i = LOG-1; i >= 0; i--) {
if (st + dist[pos][i][0] >= lim) continue;
st += dist[pos][i][0];
pos = nxt[pos][i][0];
}
return st + p[pos] + win[l[pos]];
}
