#include <bits/stdc++.h>
#include "dungeons.h"
//#define DEBUGGING
void __print(int i) { std::cerr << i; }
void __print(const char *c) {std::cerr << c; }
void __print(long long i) { std::cerr << i; }
template<typename T>
void __print(const T& t) { std::cerr << "{"; int f = 0; for (const auto& i : t) { std::cerr << (f++ ? ", " : ""); __print(i); } std::cerr << "}"; }
void _print() { std::cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...); }
#ifdef DEBUGGING
#define debug(x...) std::cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...)
#endif
constexpr static int MXSIZE = 50001;
constexpr static int MXLOG = 25;
constexpr static long long INF = 1e18;
constexpr static int BIG = 1e8;
constexpr static int MXNUM = 1e7;
// Interval, step, current index
int blp[MXLOG][MXLOG][MXSIZE];
long long blc[MXLOG][MXLOG][MXSIZE];
long long blm[MXLOG][MXLOG][MXSIZE]; // minimum needed for change
std::vector<int> s, w, p, l;
int n;
int sub(int a, long long b)
{
if (b > a)
return 0;
return a - b;
}
void init(int nn, std::vector<int> ss, std::vector<int> pp, std::vector<int> ww, std::vector<int> ll)
{
n = nn;
s = ss;
w = ww;
p = pp;
l = ll;
for (int i = 0; i < MXLOG; i++)
{
// For numbers bigger than or equal to 1<<i but smaller than 1<<(i+1)
for (int j = 0; j < n; j++)
{
if (s[j] <= (1<<i))
{
blp[i][0][j] = w[j];
blc[i][0][j] = s[j];
blm[i][0][j] = INF;
}
else
{
blp[i][0][j] = l[j];
blc[i][0][j] = p[j];
blm[i][0][j] = s[j];
}
}
blp[i][0][n] = n;
blc[i][0][n] = 0;
blm[i][0][n] = 0;
for (int j = 1; j < MXLOG; j++)
{
for (int k = 0; k <= n; k++)
{
int nxt = blp[i][j-1][k];
blp[i][j][k] = blp[i][j-1][nxt];
blc[i][j][k] = blc[i][j-1][k] + blc[i][j-1][nxt];
blm[i][j][k] = std::min(blm[i][j-1][k], blm[i][j-1][nxt] - blc[i][j-1][k]);
}
}
}
}
long long simulate(int x, int zz)
{
long long z = zz;
debug(x);
for (int i = 0; i < MXLOG; i++)
{
debug(i, x, z);
for (int j = MXLOG-1; j >= 0; j--)
{
if (blm[i][j][x] > z)
{
z += blc[i][j][x];
x = blp[i][j][x];
}
}
if (x < n && z >= s[x])
{
z += s[x];
x = w[x];
}
else if (x < n)
{
z += p[x];
x = l[x];
}
}
debug(x, n);
assert(x == n);
return z;
}
