#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*1e4+5;
const int logg=30;
int n;
vector<int> s,p,w,l,h;
vector<long long> v;
int c,done[maxn];
long long sum[maxn][32][10];
int ver[maxn][32][10];
int construct(long long x)
{
if(done[x])return done[x];
c++;
done[x]=c;
x=v[x];
for(int i=0; i<n; i++)
{
if(x>s[i])
{
ver[i][0][c]=w[i];
sum[i][0][c]=s[i];
}
else
{
ver[i][0][c]=l[i];
sum[i][0][c]=p[i];
}
}
ver[n][0][c]=n;
for(int j=1; j<=logg; j++)
for(int i=0; i<=n; i++)
{
sum[i][j][c]=sum[i][j-1][c]+sum[ver[i][j-1][c]][j-1][c];
if(1e18-sum[i][j-1][c]<sum[ver[i][j-1][c]][j-1][c])sum[i][j][c]=1e18;
ver[i][j][c]=ver[ver[i][j-1][c]][j-1][c];
//cout<<ver[i][j][num]<<" "<<i<<" "<<(1<<j)<<endl;
}
return c;
}
void init(int N, std::vector<int> S, std::vector<int> P, std::vector<int> W, std::vector<int> L)
{
n=N;
s=S;
p=P;
w=W;
l=L;
h=s;
sort(h.begin(),h.end());
v= {h[0]};
for(int i=1; i<h.size(); i++)
if(h[i]!=h[i-1])v.push_back(h[i]);
v.push_back(1e18);
return;
}
long long simulate(int x, int zz)
{
long long z=zz;
long long num=0;
while(num<v.size()&&x!=n)
{
while(num<v.size()&&z>=v[num])num++;
//cout<<x<<" "<<z<<" "<<v[num]<<endl;
int i=construct(num);
for(int j=logg;j>=0;j--)
{
if(z<v[num]-sum[x][j][i])
{
z+=sum[x][j][i];
x=ver[x][j][i];
}
}
if(x==n)return z;
z+=sum[x][0][i];
x=ver[x][0][i];
}
return z;
}
/*int main()
{
while(1)
{
int nn=100;
vector<int> ss,pp,ww,ll;
int r=1e7;
for(int i=0;i<nn;i++)
ss.push_back(r);
for(int i=0;i<nn;i++)
pp.push_back(rand()%10);
for(int i=0;i<nn;i++)
ww.push_back(min(nn,rand()%2+1+i));
for(int i=0;i<nn;i++)
ll.push_back(rand()%(nn+1));
init(nn,ss,pp,ww,ll);
cout<<nn<<" "<<5<<endl;
for(int i=0;i<ss.size();i++)
cout<<ss[i]<<" ";
cout<<endl;
for(int i=0;i<pp.size();i++)
cout<<pp[i]<<" ";
cout<<endl;
for(int i=0;i<ww.size();i++)
cout<<ww[i]<<" ";
cout<<endl;
for(int i=0;i<ll.size();i++)
cout<<ll[i]<<" ";
cout<<endl;
for(int i=1;i<=5;i++)
{
int xx,zz;
xx=rand()%nn;
zz=rand()%10;
cout<<xx<<" "<<zz<<endl;
cout<<simulate(xx,zz)<<endl;
}
}
}*/
