#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+6;
struct trie
{
char what[MAXN];
int sz[MAXN];
int nxt[MAXN];
int cur;
int par[MAXN][20];
void add_letter(char c)
{
nxt[cur]=cur+1;
par[cur+1][0]=cur;
sz[cur+1]=sz[cur]+1;
cur++;
what[cur]=c;
for(int step=1;step<20;step++)
{
par[cur][step]=par[par[cur][step-1]][step-1];
}
}
void undoOperations(int u)
{
nxt[cur+1]=nxt[cur-u];
par[nxt[cur+1]][0]=cur+1;
for(int j=0;j<20;j++)par[cur+1][j]=par[cur-u][j];
nxt[par[cur+1][0]]=cur+1;
what[cur+1]=what[cur-u];
sz[cur+1]=sz[cur-u];
cur++;
}
char GetLetter(int p)
{
int d=sz[cur]-p,c1=cur;
for(int i=0;i<20;i++)
{
if(d&(1<<i))c1=par[c1][i];
}
//cout<<sz[cur]<<" "<<p<<" "<<d<<endl;
return what[c1];
}
void print()
{
cout<<cur<<" "<<what[cur]<<endl;
}
}t;
char last;
void Init() {
t.cur=0;
}
void TypeLetter(char L) {
t.add_letter(L);
}
void UndoCommands(int U) {
t.undoOperations(U);
}
char GetLetter(int P) {
return t.GetLetter(P+1);
}
/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/
