#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int S[400005];
int P[400005];
int W[400005];
int L[400005];
int N;
long long score[400005];
long long winScore[400005];
bool visited[400005];
bool inStack[400005];
int cycleIndx[400005];
int cycleIndx2[400005];
vector<int> cycleList[400005];
vector<long long> prefixSum[400005];
vector<int> stack1;
int cnt1 = 0;
void dfs(int u){
//printf("dfs(%d)\n", u);
if(visited[u]){return;}
visited[u] = true;
stack1.push_back(u);
inStack[u] = true;
/*printf("Stack1: ");
for(int i: stack1){
printf("%d ", i);
}
printf("\n");*/
int v = L[u];
if(visited[v] && inStack[v]){
long long score2 = 0;
int indx = (int)stack1.size()-1;
while(indx >= 0){
inStack[stack1[indx]] = false;
//printf("%d\n", stack1[indx]);
if(stack1[indx] == v){break;}
indx --;
}
assert(indx >= 0);
for(int i = max(indx, 0); i < (int)stack1.size(); i ++){
score2 += P[stack1[i]];
}
for(int i = max(indx, 0); i < (int)stack1.size(); i ++){
score[stack1[i]] = score2;
cycleIndx[stack1[i]] = cnt1;
cycleIndx2[stack1[i]] = i-(indx+1);
cycleList[cnt1].push_back(stack1[i]);
//printf("cnt1=%d stack1[i]=%d\n", cnt1, stack1[i]);
}
cnt1 ++;
while((int)stack1.size() > indx){
stack1.pop_back();
}
}else{
dfs(v);
}
}
void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
N = n;
for(int i = 0; i < N; i ++){
S[i] = s[i];
P[i] = p[i];
W[i] = w[i];
L[i] = l[i];
}
memset(visited, false, sizeof(visited));
memset(score, -1, sizeof(score));
memset(cycleIndx, -1, sizeof(cycleIndx));
for(int i = 0; i < N; i ++){
if(!visited[i]){
for(int j: stack1){
inStack[j] = false;
}
stack1 = vector<int>();
dfs(i);
}
}
winScore[N] = 0;
for(int i = N-1; i >= 0; i --){
winScore[i] += winScore[W[i]] + S[i];
}
for(int i = 0; i < cnt1; i ++){
//printf("i=%d\n", i);
prefixSum[i].push_back(0);
//printf("i=%d\n", i);
for(int j: cycleList[i]){
//printf("j=%d\n", j);
prefixSum[i].push_back(prefixSum[i].back() + P[j]);
//printf("%d %lld %d\n", i, prefixSum[i].back(), j);
}
assert(cycleList[i].size());
assert(prefixSum[i].back() == score[cycleList[i][0]]);
}
//printf("here\n");
return;
}
long long op = 0;
long long simulate(int x, int z) {
long long ans = z;
int cur = x;
if(score[cur] > 0 && ans + score[cur] < S[cur]){
long long req = S[cur] - ans;
if(req > 0){
long long cnt = req/score[cur];
ans += cnt*score[cur];
}
}
while(cur != N){
//op ++;
//printf("cur=%d ans=%lld\n", cur, ans);
if(ans >= S[cur]){
//ans += S[cur];
//cur = W[cur];
ans += winScore[cur];
break;
}else{
//int i = cycleIndx[cur];
//int indx = cycleIndx2[cur];
//long long req = (S[cur] - ans + prefixSum[i][indx+1]) % score[cur];
ans += P[cur];
cur = L[cur];
}
}
//assert(op <= 2500000000);
return ans;
}
