#define MAXN 1000003
#include "stdio.h"
void Init() {}
const int LOGN=20;
int nd,now,P[MAXN][LOGN],tree[MAXN][26];
int where[MAXN],id,lvl[MAXN];
char arr[MAXN];
char get(int x){int tmp=now;
for(int i=LOGN-1;i>=0;i--)
if(x>=(1<<i))
tmp=P[tmp][i],x-=(1<<i);
return arr[tmp];
}
void TypeLetter(char L) {
if(!tree[now][L-'a']){
tree[now][L-'a']=++nd;
arr[nd]=L;
}
int to=tree[now][L-'a'];
P[to][0]=now;lvl[to]=lvl[now]+1;now=to;
for(int i=1;i<LOGN;i++)
if(P[now][i-1])
P[now][i]=P[P[now][i-1]][i-1];
where[++id]=now;
//printf("ADD %d\n",now);
}
void UndoCommands(int U) {
now=where[id-U];where[++id]=now;
//printf("UNDO %d\n",now);
}
char GetLetter(int P) {
//printf("%d %d\n",now,lvl[now]);
return get(lvl[now]-P-1);
}
