#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=5e4+10;
vector<ll> pw,pl,Gw,Gl;
int nd;
map<int,int> m,m1;
bool ci[MAX_N];
int in[MAX_N];
ll sum[MAX_N];
int en[MAX_N],sta[MAX_N];
int dis[MAX_N];
int no=0;
ll sc;
vector<ll> cis;
int ciclo(int u){
if(ci[u]) return u;
ci[u]=1;
return ciclo(Gl[u]);
}
int dfs(int x,int p,int s,bool sw){
if(ci[x]!=sw || m[x]!=-1) return m[p];
m[x]=no; m1[no]=x; no++;
int u=m[x];
sum[u]=sum[m[p]]+pl[x];
sta[u]=m[s];
return en[u]=dfs(Gl[x],x,s,sw);
}
int distan(int u){
if(u==nd) return 0;
int x=m[u];
if(dis[x]!=-1) return dis[x];
return dis[x]=distan(Gw[u])+1;
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
memset(in,0,sizeof in);
memset(ci,0,sizeof ci);
memset(dis,-1,sizeof dis);
nd=n;
sc=s[0];
dis[n]=0;
for(int i=0;i<n;i++){
m[i]=-1;
pw.push_back(s[i]);
pl.push_back(p[i]);
Gw.push_back(w[i]);
Gl.push_back(l[i]);
in[l[i]]++;
}
int cu=ciclo(0);
memset(ci,0,sizeof ci);
ciclo(cu);
for(int i=0;i<n;i++){
if(in[i]==0){
dfs(i,i,i,ci[i]);
}
}
for(int i=0;i<n;i++){
if(ci[i]) dfs(i,i,i,ci[i]);
}
for(int i=0;i<n;i++){
if(dis[m[i]]==-1) {
distan(i);
}
}
// for(auto &v:m) cout<<v.first<<": "<<v.second<<endl;
}
int binary(int l,int r,ll z,ll a){
// int l=u,r=en[u]+1;
ll d;
while(r-l>1){
int mid=(l+r)/2;
d=sum[mid]-a;
if(z+d>=sc) r=mid;
else l=mid;
}
d=sum[l]-a;
if(z+d>=sc) r=l;
return r;
}
long long simulate(int x, int zr) {
int u=m[x];
ll a=0;
ll z=zr;
if(u!=sta[u])
a=sum[u-1];
ll d=sum[en[u]]-a;
if(z+d>=sc){
u=binary(u,en[u]+1,z,a);
z+=sum[u]-a;
}
else{
z+=d;
//u=m[Gw[en[u]]];
ll vu=(sc-z)/sum[en[u]];
z+=vu*sum[en[u]];
if(u==sta[u]) a=0;
else a=sum[u-1];
if(z+sum[en[u]]-a>=sc){
u=binary(u,en[u]+1,z,a);
z+=sum[u]-a;
}
else{
z+=sum[en[u]]-a;
u=binary(sta[u],u,z,a);
z+=sum[u];
}
}
u=m[Gl[m1[u]]];
z+=sc*dis[u];
return z;
}
