#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<vector<vector<vector<ll>>>> binary;//index, +, max excluded
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
s.push_back(0);
p.push_back(0);
w.push_back(n);
l.push_back(n);
n++;
for (int range = 0; range < 25; range++)
{
ll r = 1 << range;
vector<vector<vector<ll>>> t = vector<vector<vector<ll>>>(n, vector<vector<ll>>(25));
for (int i = 0; i < n; i++)
{
if (s[i] <= r) {
t[i][0] = {w[i], s[i], LLONG_MAX};
} else {
t[i][0] = {l[i], p[i], s[i]};
}
}
for (int i = 1; i < 25; i++)
{
for (int ind = 0; ind < n; ind++)
{
ll pointer = t[ind][i - 1][0];
t[ind][i] = {t[pointer][i - 1][0], t[ind][i - 1][1] + t[pointer][i - 1][1], min(t[ind][i - 1][2], t[pointer][i - 1][2] - t[ind][i - 1][1])};
}
}
binary.push_back(t);
}
}
long long simulate(int x, int z) {
for (int r = 0; r < 25; r++)
{
for (int s = 24; s >= 0; s--)
{
if (binary[r][x][s][2] > z) {
z += binary[r][x][s][1];
x = binary[r][x][s][0];
}
}
}
return z;
}
