#include "dungeons.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int>w,l,s,p,v;
struct pom{
long long nxt,sum;
};
vector<vector<vector<pom>>>lca;
void init(int N,vector<int> S,vector<int> P,vector<int> W,vector<int> L) {
n=N;
l=L;
s=S;
p=P;
w=W;
s.push_back(0);
l.push_back(n);
w.push_back(n);
p.push_back(0);
map<int,int>mp;
for(int i=0;i<n;i++)
{
if(mp[s[i]]==0)
{
mp[s[i]]=1;
v.push_back(s[i]);
}
}
v.push_back(0);
sort(v.begin(),v.end());
lca.resize(v.size(),vector<vector<pom>>(n+1,vector<pom>(25)));
for(int i1=0;i1<v.size();i1++)
{
long long k=v[i1];
for(int j=0;j<25;j++)
{
for(int i=0;i<=n;i++)
{
if(j==0)
{
if(k>=s[i])
{
lca[i1][i][j].nxt=w[i];
lca[i1][i][j].sum=s[i];
}
else
{
lca[i1][i][j].nxt=l[i];
lca[i1][i][j].sum=p[i];
}
}
else
{
int a=lca[i1][i][j-1].nxt;
lca[i1][i][j].nxt=lca[i1][a][j-1].nxt;
lca[i1][i][j].sum=lca[i1][i][j-1].sum+lca[i1][a][j-1].sum;
}
}
}
}
return;
}
long long simulate(int x, int z) {
long long sum=z;
for(int i=0;i<v.size()-1;i++)
{
if(sum>=v[i+1])continue;
for(int j=24;j>=0;j--)
{
if(sum+lca[i][x][j].sum<v[i+1])
{
sum+=lca[i][x][j].sum;
x=lca[i][x][j].nxt;
}
}
sum+=lca[i][x][0].sum;
x=lca[i][x][0].nxt;
}
sum+=lca[v.size()-1][x][24].sum;
return sum;
}
