#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int N, S[400005], P[400005], W[400005], L[400005];
pair<int,long long> lose[400005][25], win[400005][25];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
N = n;
for (int i = 0; i < N; ++i)
S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i], lose[i][0] = make_pair(L[i],P[i]), win[i][0] = make_pair(W[i],S[i]);
lose[N][0] = win[N][0] = make_pair(-1,-1);
for (int k = 1; k < 25; ++k) for (int i = 0; i <= N; ++i) {
if (lose[i][k-1] == make_pair(-1,-1ll)) lose[i][k] = make_pair(-1,-1);
else {
lose[i][k].first = lose[lose[i][k-1].first][k-1].first;
if (lose[i][k].first == -1) lose[i][k].second = -1;
else lose[i][k].second = lose[i][k-1].second + lose[lose[i][k-1].first][k-1].second;
}
if (win[i][k-1] == make_pair(-1,-1ll)) win[i][k] = make_pair(-1,-1);
else {
win[i][k].first = win[win[i][k-1].first][k-1].first;
if (win[i][k].first == -1) win[i][k].second = -1;
else win[i][k].second = win[i][k-1].second + win[win[i][k-1].first][k-1].second;
}
}
}
long long simulate(int x, int z) {
long long ans = z;
for (int k = 24; k >= 0; --k)
if (lose[x][k] != make_pair(-1,-1ll) && ans+lose[x][k].second < S[0])
ans += lose[x][k].second, x = lose[x][k].first;
ans += lose[x][0].second, x = lose[x][0].first;
for (int k = 24; k >= 0; --k)
if (win[x][k] != make_pair(-1,-1ll))
ans += win[x][k].second, x = win[x][k].first;
return ans;
}
