#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int lose[400005], win[500005];
int he[400005], loseget[400005];
int n;
bool sub2 = 1;
bool sub4 = 1;
struct s2tag {
int en;
ll enExp;
ll gap;
} s2fw[12][11][400005];
// s2fw[i][j][k] = from k, beat all <4^i, go 4^j steps
// gap: least amount of health you need to begin with for s2fw[i][j][k] to not
// work
ll p5[30];
s2tag mer(s2tag a, s2tag b) {
return {b.en, a.enExp + b.enExp, max(0ll, min(a.gap, b.gap - a.enExp))};
}
#define ex4(n) p5[n]
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w,
std::vector<int> l) {
p5[0] = 1;
for (int i = 1; i <= 24; i++)
p5[i] = p5[i - 1] * 5;
::n = n;
for (int i = 0; i < n; i++) {
lose[i] = l[i];
win[i] = w[i];
he[i] = s[i];
loseget[i] = p[i];
if (he[i] != loseget[i])
sub2 = 0;
}
win[n] = n;
for (int i = 0; i < 12; i++) {
for (int k = 0; k <= n; k++) {
if (he[k] < ex4(i))
s2fw[i][0][k] = {win[k], he[k], 1ull << 60};
else
s2fw[i][0][k] = {lose[k], loseget[k], he[k]};
}
for (int j = 0; j < 10; j++)
for (int k = 0; k <= n; k++) {
s2fw[i][j + 1][k] = s2fw[i][j][k];
for (int _ = 0; _ < 4; _++)
s2fw[i][j + 1][k] =
mer(s2fw[i][j + 1][k], s2fw[s2fw[i][j + 1][k].en][j][k]);
}
}
return;
}
long long simulate(int x, int _z) {
ll z = _z;
while (x != n) {
int r = 0;
while (ex4(r + 1) < z)
r++;
r = min(r, 12);
for (int j = 0; j >= 0; j--)
for (int _ = 0; _ < 4; _++)
if (mer(s2tag{x, z, 1ll << 60}, s2fw[r][j][x]).gap > 0) {
z += s2fw[r][j][x].enExp;
x = s2fw[r][j][x].en;
}
if (z >= he[x]) {
z += he[x];
x = win[x];
} else {
// assert(0);
z += loseget[x];
x = lose[x];
}
}
return z;
}
