#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F3F3F3F3F
const int MXN = 4e5 + 5;
const int LOG = 25;
const int LG = 8;
int N;
long long p[LOG][LG][MXN], mn[LOG][LG][MXN], gain[LOG][LG][MXN];
struct Tree
{
int id;
void init()
{
for (int lg = 1; lg < LG; lg++)
{
for (int i = 0; i <= N; i++)
{
mn[id][lg][i] = mn[id][lg - 1][i];
gain[id][lg][i] = gain[id][lg - 1][i];
p[id][lg][i] = p[id][lg - 1][i];
for (int j = 1; j < 8; j++)
{
mn[id][lg][i] = min(mn[id][lg][i], mn[id][lg - 1][p[id][lg][i]] - gain[id][lg][i]);
gain[id][lg][i] = gain[id][lg][i] + gain[id][lg - 1][p[id][lg][i]];
p[id][lg][i] = p[id][lg - 1][p[id][lg][i]];
}
}
}
}
void move(int &x, long long &val)
{
if (x == N) return;
for (int i = LG - 1; i >= 0; i--)
{
for (int j = 0; j < 8; j++)
{
if (val < mn[id][i][x])
{
val += gain[id][i][x];
x = p[id][i][x];
}
else break;
}
}
}
};
Tree t[LOG];
vector<long long> S, P, W, L;
void init(int n, vector<int> s1, vector<int> p1, vector<int> w1, vector<int> l1)
{
N = n;
for (int &i : s1) S.push_back(i);
for (int &i : p1) P.push_back(i);
for (int &i : w1) W.push_back(i);
for (int &i : l1) L.push_back(i);
for (int i = 0; i < LOG; i++)
{
t[i].id = i;
for (int j = 0; j < N; j++)
{
if (s1[j] < (1LL << i))
{
p[i][0][j] = w1[j];
gain[i][0][j] = s1[j];
mn[i][0][j] = inf;
}
else
{
p[i][0][j] = l1[j];
gain[i][0][j] = p1[j];
mn[i][0][j] = s1[j];
}
}
p[i][0][N] = N, gain[i][0][N] = 0, mn[i][0][N] = -inf;
t[i].init();
}
}
long long simulate(int x, int z)
{
long long val = z;
while (x != N)
{
int lg = 0;
long long tmp = val;
while (tmp > 1) lg++, tmp >>= 1;
lg = min(lg, LOG - 1);
t[lg].move(x, val);
if (x == N) break;
val += S[x];
x = W[x];
}
return val;
}
