#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 400007
using namespace std;
int n,parent[MAXN],to[MAXN],last,comp[MAXN];
int win[MAXN],lose[MAXN],k;
vector<int> v[MAXN];
long long curr,dist[MAXN],pref,minloops,tocomp[MAXN];
int pos[MAXN];
pair<int,int> dp[MAXN][20];
bool li[MAXN][20];
pair<int,int> ff(int x,int p){
if(x==0)return {n,0};
if(p==0)return {parent[x],win[parent[x]]};
if(li[x][p])return dp[x][p];
li[x][p]=true;
dp[x][p].first=ff(ff(x,p-1).first,p-1).first;
dp[x][p].second=max( ff(x,p-1).second , ff(ff(x,p-1).first,p-1).second );
return dp[x][p];
}
void dfs(int x,long long len){
len+=win[x]; dist[x]=len;
for(int i=0;i<v[x].size();i++){
dfs(v[x][i],len);
}
}
bool in[MAXN],dali,incyc[MAXN];
vector< vector<int> > cycle;
long long sum[MAXN];
int stop;
void dfs2(int x){
if(comp[to[x]]!=0){
comp[x]=comp[to[x]];
return;
}
in[x]=true;
if(in[to[x]]){
k++; comp[x]=k; stop=to[x];
cycle.push_back({x}); dali=true;
in[x]=false; sum[k]=lose[x]; incyc[x]=true;
return;
}
dfs2(to[x]);
comp[x]=comp[to[x]];
if(dali){
incyc[x]=true;
cycle[comp[x]].push_back(x);
sum[comp[x]]+=lose[x];
}
if(x==stop)dali=false;
}
void init(int N,vector<int> s,vector<int> p,vector<int> w,vector<int> l){
n=N;
for(int i=0;i<n;i++){
parent[i]=w[i];
v[parent[i]].push_back(i);
to[i]=l[i];
win[i]=s[i]; lose[i]=p[i];
}
parent[n]=n;
dfs(n,0);
cycle.push_back({});
for(int i=0;i<n;i++){
if(comp[i]==0){
dali=false; stop=-1;
dfs2(i);
}
}
for(int i=0;i<=k;i++){
reverse(cycle[i].begin(),cycle[i].end());
for(int f=0;f<cycle[i].size();f++){
pos[cycle[i][f]]=f;
if(to[cycle[i][f]]!=cycle[i][(f+1)%int(cycle[i].size())])cout<<1/0;
}
}
}
long long simulate(int x, int z){
curr=z;
while(x!=n){
while(curr<win[x] and !incyc[x]){
curr+=lose[x]; x=to[x];
}
if(curr<win[x]){
minloops=100000000; pref=0;
for(int i=pos[x];i<cycle[comp[x]].size();i++){
minloops=min( minloops, int( ceil(1.0*(win[cycle[comp[x]][i]]-curr-pref)/sum[comp[x]]) )*1LL );
//pref+=lose[cycle[comp[x]][i]];
}
for(int i=0;i<pos[x];i++){
minloops=min( minloops, int( ceil(1.0*(win[cycle[comp[x]][i]]-curr-pref)/sum[comp[x]]) )*1LL );
//pref+=lose[cycle[comp[x]][i]];
}
minloops--;
if(minloops<0)minloops=0;
curr+=minloops*sum[comp[x]];
while(curr<win[x]){
curr+=lose[x]; x=to[x];
}
}
last=x;
for(int i=19;i>=0;i--){
if(ff(x,i).first!=n and ff(x,i).second<=curr){
x=ff(x,i).first;
}
}
curr+=dist[last]-dist[parent[x]];
x=parent[x];
}
return curr;
}
/*
int main(){
init(3, {2, 6, 9}, {3, 1, 2}, {2, 2, 3}, {1, 0, 1});
cout<<simulate(0,1)<<"\n";
cout<<simulate(2,3)<<"\n";
}
*/
