#include "dungeons.h"
#include <vector>
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
ll n,s[400005],p[400005],w[400005],l[400005],smax;
bool sub2=0,sub4=0;
vector<ll> mys;
struct date
{
ll maxim,poz,suma;
} dp[400005][22],whereL[400005],whereR[400005];
ll getver(ll x)
{
for(int i=0;i<mys.size();i++)
if(mys[i]>x)
return i;
return mys.size();
}
pll ver[7][400005][22]; // {suma,poz}
date tour(ll poz,ll val)
{
if(dp[poz][20].maxim<=val)
return {0,n,dp[poz][20].suma};
ll suma=0;
for(ll j=20;j>=0;j--)
if(dp[poz][j].maxim<=val)
{
suma+=dp[poz][j].suma;
poz=w[dp[poz][j].poz];
}
return {0,poz,suma};
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
n=N;
sub2=1;
for(int i=0;i<n;i++)
{
s[i]=S[i];
mys.push_back(s[i]);
smax=max(smax,s[i]);
p[i]=P[i];
if(s[i]!=p[i])
sub2=0;
w[i]=W[i];
l[i]=L[i];
}
sort(mys.begin(),mys.end());
mys.erase(unique(mys.begin(),mys.end()),mys.end());
w[n]=n;
if(mys.size()<=5)
{
sub4=1;
for(int v=0;v<=mys.size();v++)
{
ll lim=1e9;
if(v<mys.size())
lim=mys[v];
for(int i=0;i<=20;i++)
ver[v][n][i]={0,n};
for(int i=0;i<n;i++)
{
if(s[i]>=lim)
{
ver[v][i][0].first=p[i];
ver[v][i][0].second=l[i];
}
else
{
ver[v][i][0].first=s[i];
ver[v][i][0].second=w[i];
}
}
for(int j=1;j<=20;j++)
{
for(int i=0;i<n;i++)
{
int poz=ver[v][i][j-1].second;
ver[v][i][j].second=ver[v][poz][j-1].second;
ver[v][i][j].first=ver[v][i][j-1].first+ver[v][poz][j-1].first;
}
}
}
}
if(sub2)
{
for(int j=0;j<=20;j++)
dp[n][j]={0,n,0};
for(int i=n-1;i>=0;i--)
{
dp[i][0]={s[i],i,s[i]};
for(int j=1;j<=20;j++)
{
ll p=w[dp[i][j-1].poz];
ll poz=dp[p][j-1].poz;
dp[i][j].poz=poz;
dp[i][j].maxim=max(dp[i][j-1].maxim,dp[p][j-1].maxim);
dp[i][j].suma=dp[i][j-1].suma+dp[p][j-1].suma;
}
}
for(int i=0;i<n;i++)
{
whereL[i]=tour(l[i],s[i]);
whereR[i]=tour(w[i],s[i]);
}
}
}
long long simulate(int x, int z)
{
ll rez=z;
if(x==n)
return rez;
if(sub4)
{
while(x!=n)
{
ll v=getver(rez);
for(ll j=20;j>=0;j--)
if(getver(ver[v][x][j].first+rez)==v)
{
rez+=ver[v][x][j].first;
x=ver[v][x][j].second;
}
if(x==n)
break;
if(rez>=s[x])
{
rez+=s[x];
x=w[x];
}
else
{
rez+=p[x];
x=l[x];
}
}
return rez;
}
if(sub2)
{
while(x!=n)
{
if(rez>=s[x])
{
rez+=s[x];
if(rez>=smax)
{
rez+=dp[w[x]][20].suma;
return rez;
}
rez+=whereR[x].suma;
x=whereR[x].poz;
}
else
{
rez+=s[x];
if(rez>=smax)
{
rez+=dp[l[x]][20].suma;
return rez;
}
rez+=whereL[x].suma;
x=whereL[x].poz;
}
}
return rez;
}
while(x!=n)
{
if(rez>=s[x])
{
rez+=s[x];
x=w[x];
}
else
{
rez+=p[x];
x=l[x];
}
}
return rez;
}
