#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define m_p make_pair
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
typedef long long ll;
const int N = 400005;
const int m = 28;
int n;
vector<int> S, P, W, L;
vector<int> t[N];
ll st[m][N];
int ut[m][N];
void dfst(int x, int j)
{
if (x == n || S[x] >= (1 << j))
{
st[j][x] = 0;
ut[j][x] = x;
}
for (int i = 0; i < sz(t[x]); ++i)
{
int h = t[x][i];
ut[j][h] = ut[j][x];
st[j][h] = st[j][x] + S[h];
dfst(h, j);
}
}
pair<int, ll> u[m][N];
void init(int NN, std::vector<int> SS, std::vector<int> PP, std::vector<int> WW, std::vector<int> LL) {
n = NN;
S = SS;
P = PP;
W = WW;
L = LL;
for (int i = 0; i < n; ++i)
{
t[W[i]].push_back(i);
}
for (int j = 0; j < m; ++j)
{
dfst(n, j);
for (int x = 0; x < n; ++x)
{
if (S[x] >= (1 << j))
{
u[j][x] = m_p(ut[j][L[x]], P[x] + st[j][L[x]]);
}
}
u[j][n] = m_p(n, 0);
}
}
long long simulate(int x, int Z) {
ll z = Z;
while (x != n)
{
for (int j = 0; j < m; ++j)
{
if (z < (1 << j))
{
z += st[j][x];
x = ut[j][x];
while (x != n && z < S[x])
{
assert(S[x] >= (1 << j));
z += u[j][x].se;
x = u[j][x].fi;
}
break;
}
}
}
return z;
}
