#include "dungeons.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
#define maxn 400005
#define lg 20
ll n;
vector<ll> g[maxn];
vector<ll> v[maxn];
ll a[maxn],b[maxn];
bool sub3 = 1;
bool sub1 = 1;
ll dis[maxn];
ll deg[maxn];
ll st[maxn][lg];
ll sum[maxn][lg];
ll cyc[maxn];
ll val[maxn];
ll len[maxn];
bool vis[maxn];
ll tsz = 0;
void dfs(ll u,ll p){
for(ll s : v[u]){
if(s==p) continue;
dis[s] = dis[u] + 1;
dfs(s,u);
}
}
void dfs2(ll u,ll p){
vis[u] = 1;
cyc[u] = tsz;
val[tsz]+=b[u];
len[tsz]++;
for(ll s : g[u]){
if(vis[s]) continue;
dfs2(s,u);
}
}
void init(int N, vector<int> s, vector<int> p, vector<int> w, vector<int> l) {
n = N;
for(ll i = 1;i<=n;i++) a[i] = s[i-1];
for(ll i = 1;i<=n;i++) b[i] = p[i-1];
for(ll i = 1;i<n;i++) sub3&=(a[i]==a[i+1]);
for(ll i = 1;i<=n;i++){
if(sub3) v[w[i-1]+1].pb(i);
else v[i].pb(w[i-1]+1);
}
for(ll i = 1;i<=n;i++) g[i].pb(l[i-1]+1);
if(sub3){
dfs(n+1,n+1);
for(ll i = 1;i<=n;i++){
for(ll j : g[i]) deg[j]++;
}
queue<ll> q;
for(ll i = 1;i<=n+1;i++) if(!deg[i]) q.push(i);
for(ll i = 1;i<=n;i++) cyc[i] = 1;
while(q.size()){
ll u = q.front();
q.pop();
cyc[u] = 0;
for(ll s : g[u]){
deg[s]--;
if(!deg[s]) q.push(s);
}
}
for(ll i = 1;i<=n;i++){
st[i][0] = g[i][0];
sum[i][0] = b[i];
}
st[n+1][0] = n+1;
for(ll j = 1;j<lg;j++){
for(ll i = 1;i<=n+1;i++){
st[i][j] = st[st[i][j-1]][j-1];
sum[i][j] = sum[i][j-1] + sum[st[i][j-1]][j-1];
}
}
for(ll i = 1;i<=n;i++){
if(!cyc[i]) continue;
if(vis[i]) continue;
++tsz;
dfs2(i,i);
}
}
return;
}
long long simulate(int x, int z) {
x++;
if(!sub3){
while(x!=n+1){
if(z>=a[x]){
z+=a[x];
x = v[x][0];
}else{
z+=b[x];
x = g[x][0];
}
}
return z;
}
if(!sub3) return 0;
ll s = a[1];
for(ll j = lg-1;j>=0;j--){
if(cyc[st[x][j]]) continue;
if(sum[x][j]+z<s) x = st[x][j];
}
if(x==n+1) return z;
if(z+b[x]>=s){
return z + b[x] + s*dis[x];
}
x = g[x][0];
if(x==n+1) return z;
z+=((s-z)/val[cyc[x]])*val[cyc[x]];
if(z==s) return s + s*dis[x];
for(ll j = lg-1;j>=0;j--){
if(sum[x][j]>val[cyc[x]]) continue;
if(z+sum[x][j]<s) x = st[x][j];
}
z+=b[x];
return z + s*dis[x];
}
/**
3 2
2 6 9
3 1 2
2 2 3
1 0 1
0 1
2 3
**/
