#include <bits/stdc++.h>
using namespace std;
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define loop1(x, i) for (int i = 1; i <= x; i++)
#define ALL(x) begin(x), end(x)
#define pb push_back
#define int long long
typedef vector<int> vi;
typedef vector<signed> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#include "dungeons.h"
int N;
vvvi par, dif;
int sCnt = 0;
vi lvls;
void init(signed n, vi32 s, vi32 p, vi32 w, vi32 l)
{
N = n;
set<int> levels = {0};
loop(n, i) levels.insert(s[i]);
sCnt = levels.size();
par = dif = vvvi(sCnt, vvi(30, vi(n + 1)));
lvls = vi(ALL(levels));
loop(sCnt, j)
{
loop(n, i)
{
if (s[i] > lvls[j])
{
par[j][0][i] = l[i];
dif[j][0][i] = p[i];
}
else
{
par[j][0][i] = w[i];
dif[j][0][i] = s[i];
}
}
dif[j][0][n] = 0;
par[j][0][n] = n;
}
loop(sCnt, j)
{
loop1(29, x)
{
loop(n + 1, i)
{
int half = par[j][x - 1][i];
par[j][x][i] = par[j][x - 1][half];
dif[j][x][i] = dif[j][x - 1][i] + dif[j][x - 1][half];
}
}
}
lvls.pb((int)4e18);
return;
}
int simulate(signed a, signed b)
{
int x = a, z = b;
loop(sCnt, j)
{
int s = lvls[j + 1];
if (z < s)
{
rev(30, i)
{
if (dif[j][i][x] + z < s && par[j][i][x] != N)
{
z += dif[j][i][x];
x = par[j][i][x];
}
}
z += dif[j][0][x];
x = par[j][0][x];
if (x == N)
return z;
}
}
return z;
}
