#include<iostream>
#include<algorithm>
#include <vector>
#include<cmath>
using namespace std;
const int MAX_N=50100;//4e5+5;
const int MAX=1e7;
const int LOG=24;
const long long INF=(1LL<<62);
int _s[MAX_N];
int _p[MAX_N];
int _w[MAX_N];
int _l[MAX_N];
int _n;
int parent[LOG][MAX_N][LOG];
long long sum[LOG][MAX_N][LOG];
long long minremain[LOG][MAX_N][LOG];
int lg2[MAX_N];
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=1;i<=_n+1;i++)
{
lg2[i]=(int)log2(i);
}
for(int i=1;i<=_n;i++)
{
W[i-1]++;L[i-1]++;
_s[i]=S[i-1];
_p[i]=P[i-1];
_w[i]=W[i-1];
_l[i]=L[i-1];
}
int sparsenum=0;
for(long long cost=1;cost<=MAX;cost*=2)
{
for(int i=1;i<=_n;i++)
{
if(_s[i]>cost)
{
parent[sparsenum][i][0]=_l[i];
sum[sparsenum][i][0]=_p[i];
minremain[sparsenum][i][0]=_s[i]-cost;
}
else
{
parent[sparsenum][i][0]=_w[i];
sum[sparsenum][i][0]=_s[i];
minremain[sparsenum][i][0]=INF;
}
}
for(int j=1;j<LOG;j++)
{
for(int i=1;i<=_n;i++)
{
parent[sparsenum][i][j]=parent[sparsenum][parent[sparsenum][i][j-1]][j-1];
sum[sparsenum][i][j]=sum[sparsenum][i][j-1]+sum[sparsenum][parent[sparsenum][i][j-1]][j-1];
minremain[sparsenum][i][j]=min(minremain[sparsenum][i][j-1],minremain[sparsenum][parent[sparsenum][i][j-1]][j-1]-sum[sparsenum][i][j-1]);
}
}
sparsenum++;
}
}
long long simulate(int x, int z)
{
x++;
long long cur=z;
long long initz=z,initx=x,begz=z,begx=x;
int sparsenum=0;
for(long long cost=1;cost<=MAX;cost*=2)
{
if(cost<=z && z<2*cost)
{
for(int j=LOG-1;j>=0;j--)
{
if(parent[sparsenum][x][j]==0 or cur+sum[sparsenum][x][j]>=2*cost or minremain[sparsenum][x][j]-cur<=0)continue;
cur+=sum[sparsenum][x][j];
x=parent[sparsenum][x][j];
}
}
if(x==_n+1)break;
if(cur<_s[x])
{
cur+=_p[x];
x=_l[x];
}
else
{
cur+=_s[x];
x=_w[x];
}
sparsenum++;
}
return cur;
while(begx!=_n+1)
{
if(begz<_s[begx])
{
begz+=_p[begx];
begx=_l[begx];
}
else
{
begz+=_s[begx];
begx=_w[begx];
}
}
if(begz!=cur)
{
cout<<_n<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_s[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_p[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_w[i]<<" ";
}
cout<<"\n";
for(int i=1;i<=_n;i++)
{
cout<<_l[i]<<" ";
}
cout<<"\n";
cout<<initx<<" "<<initz<<"\n";
exit(0);
}
return cur;
}
