#include <bits/stdc++.h>
#define ll long long
#define sz(x) int(x.size())
#define forn(i, n) for (i = 0; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define fr first
#define se second
using namespace std;
const int MAXN = 4e5 + 1;
const int LOG = 20;
ll up[MAXN][LOG], ma[MAXN][LOG], ma2[MAXN][LOG], sum[MAXN][LOG], up2[MAXN][LOG], sum2[MAXN][LOG], sumk[6][MAXN][LOG];
vector<int> S, P, W, L, dif;
int N;
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l)
{
s.pb(0);
p.pb(0);
w.pb(n);
l.pb(n);
ll i, j;
N = n;
S = s;
P = p;
W = w;
L = l;
map<ll, bool> m;
for (i = 0; i < n; i++)
{
if (m[s[i]] == 0)
dif.pb(s[i]);
m[s[i]] = 1;
}
sort(all(dif));
for (i = 0; i <= n; i++)
{
up[i][0] = l[i];
up2[i][0] = w[i];
ma[i][0] = s[i];
ma2[i][0] = s[i];
sum[i][0] = p[i];
sum2[i][0] = s[i];
for (j = 0; j < sz(dif); j++)
{
sumk[j][i][0] = ((s[i] == dif[j]) ? 1 : 0);
}
}
for (i = 1; i < LOG; i++)
{
for (j = 0; j <= n; j++)
{
up[j][i] = up[up[j][i - 1]][i - 1];
up2[j][i] = up2[up2[j][i - 1]][i - 1];
sum[j][i] = sum[j][i - 1] + sum[up[j][i - 1]][i - 1];
sum2[j][i] = sum2[j][i - 1] + sum2[up2[j][i - 1]][i - 1];
ma[j][i] = max(ma[j][i - 1], ma[up2[j][i - 1]][i - 1]);
ma2[j][i] = max(ma2[j][i - 1], ma2[up[j][i - 1]][i - 1]);
for (ll k = 0; k < sz(dif); k++)
{
sumk[k][j][i] = sumk[k][j][i-1]+sumk[k][up[j][i - 1]][i - 1];
}
}
}
return;
}
long long simulate(int x, int z)
{
ll act = z, i, ult;
while (x != N)
{
if (1ll * S[x] <= act)
{
ll aum = 0;
for (i = LOG - 1; i >= 0; i--)
{
if (ma[x][i] <= act)
{
aum += sum2[x][i];
x = up2[x][i];
}
}
act += aum;
}
else
{
ll miz = LLONG_MAX, nx = 0, ak = 0;
for (auto k : dif)
{
ll nod = x, nz = act;
for (i = LOG - 1; i >= 0; i--)
{
if (nz + sum[nod][i] < k)
{
nz += sum[nod][i];
nod = up[nod][i];
}
}
if (nz < k)
{
nz += sum[nod][0];
nod = up[nod][0];
}
// calcular al siguiente k
if (sumk[ak][nod][LOG - 1] == 0)
{
ak++;
continue;
}
for (i = LOG - 1; i >= 0; i--)
{
if (sumk[ak][nod][i] == 0)
{
nz += sum[nod][i];
nod = up[nod][i];
}
}
/////////
if (miz > nz)
{
miz = nz;
nx = nod;
}
ak++;
}
if (up[x][LOG - 1] == N)
{
ll nod = x, nz = act;
for (i = LOG - 1; i >= 0; i--)
{
if (up[nod][i] != N)
{
nz += sum[nod][i];
nod = up[nod][i];
}
}
nz += sum[nod][0];
nod = up[nod][0];
if (miz > nz)
{
miz = nz;
nx = nod;
}
}
act = miz;
x = nx;
}
}
return act;
}
