#include<iostream>
using namespace std;
struct Trie{
int ch[26],par[20];
int depth;
char c;
};
int curr;
int ct=2;
Trie tries[2000000];
int strs[1000000];
void Init(){
for(int i=0;i<20;i++)
tries[1].par[i]=1;
}
void TypeLetter(char L){
curr++;
strs[curr]=strs[curr-1];
int l=L-'a';
if(tries[strs[curr]].ch[l]==0){
tries[ct].depth=tries[strs[curr]].depth+1;
tries[ct].c=L;
tries[ct].par[0]=strs[curr];
for(int i=1;i<20;i++)
tries[ct].par[i]=tries[tries[ct].par[i-1]].par[i-1];
tries[strs[curr]].ch[l]=ct++;
}
strs[curr]=tries[strs[curr]].ch[l];
}
void UndoCommands(int U){
curr++;
strs[curr]=strs[curr-U-1];
}
char GetLetter(int P){
int ct=strs[curr];
for(int i=19;i>=0;i--){
if(tries[tries[ct].par[i]].depth>P)
ct=tries[ct].par[i];
}
return tries[ct].c;
}
