#include <iostream>
using namespace std;
const int MAXT=2e6+100;
const int LG=21;
int tm=1;
int par[MAXT][LG];
int len[MAXT];
char cp[MAXT];
void Init()
{
for(int j=0;j<1000;j++)
cp[j]='$';
}
void TypeLetter(char L)
{
cp[tm]=L;
len[tm]=len[tm-1]+1;
par[tm][0]=tm-1;
for(int j=1;j<LG;j++)
par[tm][j]=par[par[tm][j-1]][j-1];
tm++;
}
void UndoCommands(int U)
{
len[tm]=len[tm-U-1];
par[tm][0]=tm-U-1;
for(int j=0;(j+1)<LG;j++)
par[tm][j+1]=par[tm-U-1][j];
tm++;
}
char GetLetter(int P)
{
int ct=tm-1;
for(int j=LG-1;j>=0;j--)
{
if(len[par[ct][j]]>P)
{
ct=par[ct][j];
}
}
return cp[ct];
}
