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