#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> S, P, W, L;
int N;
const int MAXN = 5e4 + 1;
vector<int> adj[MAXN + 1];
ll cost[MAXN + 1];
ll cycle_cost[MAXN + 1];
bool cycle[MAXN + 1];
int lift[MAXN + 1][20], lift1[MAXN + 1][20];
ll cost1[MAXN + 1][20];
ll cyc_cost[MAXN + 1][20];
int len[MAXN + 1];
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
S = s;
P = p;
W = w;
L = l;
S.push_back(0);
for (int i = 0; i < n; ++i) {
adj[w[i]].push_back(i);
}
auto dfs = [&](auto& dfs, int i, ll now) -> void {
now += S[i];
cost[i] = now;
for (auto& u : adj[i]) {
dfs(dfs, u, now);
}
};
dfs(dfs, n, 0);
// for (int i = 0; i < n; ++i) {
// cerr << cost[i] << " ";
// }
// cerr << "\n";
vector<bool> vis(n);
for (int i = 0; i < n; ++i) {
if (vis[i]) continue;
int j = i;
while (!vis[j]) {
vis[j] = true;
j = L[j];
}
if (cycle[j]) continue;
int y = j;
ll tot = 0;
// cerr << y << "\n";
bool ok = true;
int now = 0;
do {
if (cycle[y] || y == n) {
ok = false;
break;
}
tot += P[y];
y = L[y];
now += 1;
} while (y != j);
if (!ok) continue;
do {
len[y] = now;
cycle[y] = 1;
cycle_cost[y] = tot;
y = L[y];
} while (y != j);
}
for (int i = 0; i <= n; ++i) {
for (int j = 0; j < 20; ++j) {
lift[i][j] = -1;
cost1[i][j] = 1e18;
cyc_cost[i][j] = 1e18;
lift1[i][j] = -1;
}
}
// for (int i = 0; i < n; ++i) {
// if (cycle[i]) {
// cerr << i << " ";
// }
// }
// cerr << "\n";
for (int i = 0; i < n; ++i) {
if (cycle[i]) continue;
lift[i][0] = L[i];
cost1[i][0] = P[i];
}
for (int i = 0; i < n; ++i) {
if (lift[L[i]][0] != -1) {
// cerr << i << " !\n";
lift[i][0] = L[i];
cost1[i][0] = P[i];
}
}
for (int j = 1; j < 20; ++j) {
for (int i = 0; i < n; ++i) {
if (lift[i][j - 1] == -1) continue;
// cerr << i << "!\n";
lift[i][j] = lift[lift[i][j - 1]][j - 1];
cost1[i][j] = cost1[i][j - 1] + cost1[lift[i][j - 1]][j - 1];
}
}
for (int i = 0; i < n; ++i) {
if (!cycle[i]) continue;
lift1[i][0] = L[i];
cyc_cost[i][0] = P[i];
}
for (int j = 1; j < 20; ++j) {
for (int i = 0; i < n; ++i) {
if (lift1[i][j - 1] == -1) continue;
if ((1LL << j) > len[i]) continue;
// cerr << i << "!\n";
lift1[i][j] = lift1[lift1[i][j - 1]][j - 1];
cyc_cost[i][j] = cyc_cost[i][j - 1] + cyc_cost[lift1[i][j - 1]][j - 1];
}
}
// for (int j = 0; j < 5; ++j) {
// for (int i = 0; i <= n; ++i) {
// cout << lift[i][j] << " ";
// }
// cout << "\n";
// }
// for (int j = 0; j < 5; ++j) {
// for (int i = 0; i <= n; ++i) {
// cout << cost1[i][j] << " ";
// }
// cout << "\n";
// }
// for (int i = 0; i <= n; ++i) {
// cout << cycle[i] << " ";
// }
// cout << "\n";
return;
}
long long simulate(int x, int z) {
ll res = z;
ll tot = 0;
// cout << x << " -> ";
if (!cycle[x]) {
for (int i = 19; i >= 0; --i) {
if (lift[x][i] == -1) continue;
if (res + cost1[x][i] >= S[0]) continue;
// cout << i << " = " << lift[x][i] << " " << cost1[x][i] << "\n";
// cerr << "a\n";
res += cost1[x][i];
x = lift[x][i];
}
// if (lift[x][0] != -1) x = lift[x][0];
// cout << x << " -> ";
while (x != N && res < S[0] && !cycle[x]) {
res += P[x];
x = L[x];
}
}
// cerr << x << "\n";
if (x == N) return res;
if (res >= S[0]) {
return res + cost[x];
}
// cerr << x << " " << res << " " << tot << "\n";
tot = cycle_cost[x];
// cerr << x << " " << cycle_cost[x] << " " << (S[0] - res) / tot * tot << "\n";
// cerr << tot << " ";
res += (S[0] - res) / tot * tot;
// cerr << res << " " << "\n";
for (int i = 19; i >= 0; --i) {
if (lift1[x][i] == -1) continue;
if (res + cyc_cost[x][i] >= S[0]) continue;
// cout << i << " = " << lift[x][i] << " " << cost1[x][i] << "\n";
// cerr << "a\n";
res += cyc_cost[x][i];
x = lift1[x][i];
}
// if (lift[x][0] != -1) x = lift[x][0];
// cout << x << " -> ";
while (x != N && res < S[0]) {
res += P[x];
x = L[x];
}
// cerr << res << " " << x << "\n";
res += cost[x];
return res;
}
