#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using v = vector<T>;
using ll = long long;
using pii = pair<int, int>;
#define cerr if(0) cerr
v<ll> S, P, L, W;
v<ll> afterwin;
v<v<v<ll>>> lift;
void init(int n, v<int> s, v<int> p, v<int> w, v<int> l) {
s.push_back(s[0]);
p.push_back(0);
l.push_back(n);
w.push_back(n);
S.resize(n+1);
P.resize(n+1);
L.resize(n+1);
W.resize(n+1);
for (int i=0; i<=n; i++) {
S[i] = s[i];
P[i] = p[i];
W[i] = w[i];
L[i] = l[i];
}
afterwin.resize(n+1);
afterwin[n] = 0;
for (int i=n-1; i >= 0; i--) {
afterwin[i] = 1+afterwin[w[i]];
}
//cerr << "? " << endl;
lift.assign(n+1, v<v<ll>>(21, v<ll>(2)));
for (int i=0; i<=n; i++) {
lift[i][0][0] = l[i];
lift[i][0][1] = p[i];
}
//cerr << "? " << endl;
for (int j=1; j<21; j++) {
for (int i=0; i<=n; i++) {
lift[i][j][0] = lift[lift[i][j-1][0]][j-1][0];
lift[i][j][1] = lift[lift[i][j-1][0]][j-1][1] + lift[i][j-1][1];
}
}
}
ll simulate(int x, int z) {
ll sum = z;
int aux = x;
int n = S.size();
cerr << S[x] << endl;
for (int i=20; i>=0; i--) {
if (x == n) continue;
if (sum+lift[x][i][1] < S[x]) {
sum += lift[x][i][1];
x = lift[x][i][0];
}
}
if (sum < S[x] && x != n) {
sum += P[x];
x = L[x];
}
cerr << x << " "<< sum << endl;
return sum + afterwin[x]*S[x];
}
