#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,curNode,nT,p[N][22],cnt,pos[N],dep[N];
char c[N];
void Init()
{
curNode=0;
cnt=0;;
memset(p,-1,sizeof p);
pos[0]=0;
nT=0;
}
void TypeLetter(char L)
{
cnt++;
nT++;
p[nT][0]=curNode;
dep[nT]=dep[curNode]+1;
c[nT]=L;
curNode=nT;
pos[cnt]=curNode;
for(int i=1;i<=21;i++) p[nT][i]=p[p[nT][i-1]][i-1];
}
void UndoCommands(int U)
{
curNode=pos[cnt-U];
cnt++;
pos[cnt]=curNode;
}
char GetLetter(int P)
{
P++;
int go=dep[curNode]-P;
int node=curNode;
for(int i=0;i<=21;i++) if(go>>i&1) node=p[node][i];
return c[node];
}
/*
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int m;
cin>>m;
while(m--)
{
int op;
cin>>op;
if(op==1)
{
char L;
cin>>L;
TypeLetter(L);
}
else if(op==2)
{
int u;
cin>>u;
UndoCommands(u);
}
else
{
int k;
cin>>k;
k++;
cout<<GetLetter(k)<<'\n';
}
}
}
*/
/*
14
1 a
1 b
3 1
1 d
2 2
2 1
3 2
1 e
2 1
2 5
1 c
3 2
2 2
3 2
*/
