#include "dungeons.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int N = 4e5 + 10, K = 30;
pair<ll, ll> jump_win[N][K], jump_lose[N][K];
ll sum_win[N][K];
ll sum_lose[N][K];
ll finish, S[N], P[N], W[N], L[N];
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
for(int i = 0; i < n; ++i) {
S[i] = s[i], P[i] = p[i], W[i] = w[i], L[i] = l[i];
}
finish = n;
for(int i = 0; i < N; ++i) {
for(int j = 0; j < K; ++j) {
jump_win[i][j] = {n, 1e17};
jump_lose[i][j] = {n, 0};
}
}
for(int i = 0; i < n; ++i) {
jump_win[i][0] = {w[i], s[i]};
sum_win[i][0] = s[i];
sum_lose[i][0] = p[i];
jump_lose[i][0] = {l[i], s[i]};
}
for(int j = 1; j < K; ++j) {
for(int i = 0; i < n; ++i) {
jump_win[i][j].first = jump_win[jump_win[i][j - 1].first][j - 1].first;
sum_win[i][j] = sum_win[i][j - 1] + sum_win[jump_win[i][j - 1].first][j - 1];
ll need1 = jump_win[i][j - 1].second;
ll need2 = jump_win[jump_win[i][j - 1].first][j - 1].second - sum_win[i][j - 1];
jump_win[i][j].second = max(need1, need2);
jump_lose[i][j].first = jump_lose[jump_lose[i][j - 1].first][j - 1].first;
sum_lose[i][j] = sum_lose[i][j - 1] + sum_lose[jump_lose[i][j - 1].first][j - 1];
need1 = jump_lose[i][j - 1].second;
need2 = jump_lose[jump_lose[i][j - 1].first][j - 1].second - sum_lose[i][j - 1];
jump_lose[i][j].second = min(need1, need2);
}
}
}
long long simulate(int x, int z) {
ll w = z;
while(x < finish) {
for(int j = K - 1; j >= 0; --j) {
if(w >= jump_win[x][j].second) {
w += sum_win[x][j];
x = jump_win[x][j].first;
}
}
if(x == finish) break;
for(int j = K - 1; j >= 0; --j) {
if(w < jump_lose[x][j].second) {
w += sum_lose[x][j];
x = jump_lose[x][j].first;
}
}
}
return w;
}
