/* https://codeforces.com/blog/entry/74847 */
#include "dungeons.h"
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 400000, L = 25; /* L = ceil(log2(10^7 + N)) + 1 */
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
int ss[N + 1], pp[N + 1], jjw[N + 1], jjl[N + 1], n;
int jj[L][N + 1], upper[L][N + 1]; long long dd[L][N + 1];
int hh[L][N + 1], jj_[L][N + 1], upper_[L][N + 1]; long long dd_[L][N + 1];
void dfs(int *jj, long long *dd, int *upper, int *hh, int *jj_, long long *dd_, int *upper_, int i) {
int j, k;
j = jj[i];
hh[i] = -1;
if (hh[j] == -1) {
hh[i] = 1, jj_[i] = -1;
j = i, dd_[i] = 0, upper_[i] = INF;
do {
upper_[i] = max(min(upper_[i], upper[j] == INF ? INF : upper[j] - dd_[i]), 0);
dd_[i] += dd[j];
} while ((j = jj[j]) != i);
} else {
if (!hh[j])
dfs(jj, dd, upper, hh, jj_, dd_, upper_, j);
hh[i] = 2, jj_[i] = j, dd_[i] = dd[i], upper_[i] = upper[i];
if (hh[j] != 1 && hh[j] == hh[k = jj_[j]]) {
hh[i] = hh[j] + 1;
jj_[i] = jj_[k];
dd_[i] += dd_[j] + dd_[k];
upper_[i] = max(min(upper_[i], upper_[j] == INF ? INF : upper_[j] - dd_[i]), 0);
upper_[i] = max(min(upper_[i], upper_[k] == INF ? INF : upper_[k] - dd_[i] - dd_[j]), 0);
}
}
}
void init(int n_, vi ss_, vi pp_, vi jjw_, vi jjl_) {
int l, i;
n = n_;
for (i = 0; i < n; i++)
ss[i] = ss_[i], pp[i] = pp_[i], jjw[i] = jjw_[i], jjl[i] = jjl_[i];
for (l = 0; l < L; l++) {
for (i = 0; i <= n; i++)
if (i == n)
jj[l][i] = n, dd[l][i] = 0, upper[l][i] = 0;
else if (ss[i] < 1 << l)
jj[l][i] = jjw[i], dd[l][i] = ss[i], upper[l][i] = INF;
else
jj[l][i] = jjl[i], dd[l][i] = pp[i], upper[l][i] = ss[i];
for (i = 0; i <= n; i++)
if (!hh[l][i])
dfs(jj[l], dd[l], upper[l], hh[l], jj_[l], dd_[l], upper_[l], i);
}
}
long long simulate(int i, int s_) {
int l;
long long s;
s = s_;
for (l = 0; l < L && i < n; l++) {
while (hh[l][i] != 1)
if (upper_[l][i] == INF || s < upper_[l][i])
s += dd_[l][i], i = jj_[l][i];
else if (upper[l][i] == INF || s < upper[l][i])
s += dd[l][i], i = jj[l][i];
else
break;
if (hh[l][i] == 1) {
if (s < upper_[l][i])
s += (upper_[l][i] - s + dd_[l][i] - 1) / dd_[l][i] * dd_[l][i];
if (upper[l][i] == INF || s < upper[l][i]) {
s += dd[l][i], i = jj[l][i], l--;
continue;
}
}
if (i < n) {
if (s >= ss[i])
s += ss[i], i = jjw[i];
else
s += pp[i], i = jjl[i];
}
}
return s;
}
