#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define mxn 1000005
using namespace std;
struct International_Olympiad_in_Informatics
{
struct trie
{
trie *p[21];
char up;
int h=0;
} *r,*node[mxn];
int n;
void Init() { r=new trie(); node[0]=r; }
void add(char ch)
{
n++;
trie *u=new trie(); node[n]=u;
u->up=ch;
u->p[0]=node[n-1]; u->h=node[n-1]->h+1;
for(int i=1;(1<<i)<=u->h;i++)
u->p[i]=u->p[i-1]->p[i-1];
}
void undo(int x)
{
n++; node[n]=node[n-1-x];
}
char get(int pos)
{
trie *u=node[n];
for(int i=Log(u->h);i>=0;i--)
if(u->p[i]!=NULL && u->p[i]->h>=pos)
{
u=u->p[i];
}
return u->up;
}
} IOI;
void Init() { IOI.Init(); }
void TypeLetter(char L) { IOI.add(L); }
void UndoCommands(int U) { IOI.undo(U); }
char GetLetter(int P) { return IOI.get(P+1); }
/*
int n,k;
char ch,type;
int main()
{
freopen("scrivener.inp","r",stdin);
freopen("scrivener.out","w",stdout);
Init();
cin>>n;
while(n--)
{
cin>>type;
if(type=='T') cin>>ch,TypeLetter(ch);
else if(type=='U') cin>>k,UndoCommands(k);
else cin>>k,cout<<GetLetter(k)<<'\n';
}
}*/
