#include <bits/stdc++.h>
#define NMAX 1000000
#define LOG 20
int cnt=0;
char litera[NMAX+1];
int lungime[NMAX+1];
int stra[LOG][NMAX+1];
void Init()
{
}
void TypeLetter(char L)
{
++cnt;
litera[cnt]=L;
if(litera[cnt-1]) stra[0][cnt]=cnt-1;
else stra[0][cnt]=stra[0][cnt-1];
lungime[cnt]=1+lungime[stra[0][cnt]];
for(int e=1; e<LOG; e++)
{
stra[e][cnt]=stra[e-1][stra[e-1][cnt]];
}
}
void UndoCommands(int U)
{
++cnt;
if(litera[cnt-1-U]) stra[0][cnt]=cnt-1-U;
else stra[0][cnt]=stra[0][cnt-1-U];
lungime[cnt]=lungime[stra[0][cnt]];
litera[cnt]=litera[stra[0][cnt]];
for(int e=1; e<LOG; e++)
{
stra[e][cnt]=stra[e-1][stra[e-1][cnt]];
}
}
char GetLetter(int P)
{
P++;
P=lungime[cnt]-P;
int poz=cnt;
for(int e=LOG-1; e>=0; e--)
{
if((1<<e)<=P)
{
poz=stra[e][poz];
P-=(1<<e);
}
}
return litera[poz];
}
