#include <bits/stdc++.h>
using namespace std;
#define N (int)1e6+1
#define maxp 22
struct ano{
char c;
int sons[26];
};
ano trie[N+1];
int curr=0;
int t=1;
int lift[N+1][maxp];
int googleChrome[N+1];
int d[N+1];
int cnt=1;
void Init() {
}
void TypeLetter(char c) {
int next=trie[curr].sons[c-'a'];
if(next==0){
trie[curr].sons[c-'a']=cnt;
d[cnt]=d[curr]+1;
trie[cnt].c=c;
lift[cnt][0]=curr;
curr=cnt;
int i;
for(i=1;i<maxp;i++)
lift[curr][i]=lift[lift[curr][i-1]][i-1];
cnt++;
}
else
curr=next;
googleChrome[t++]=curr;
// cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}
void UndoCommands(int n) {
curr=googleChrome[t-n-1];
// int i;
// for(i=1;i<t;i++)
// cout<<googleChrome[i]<<" ";
// cout<<endl;
googleChrome[t++]=curr;
//cout<<t<<" "<<curr<<" "<<trie[curr].c<<endl;
}
char GetLetter(int x) {
//cout<<d[curr]<<" "<<curr<<endl;
int k=d[curr]-x-1;
int i;
int ans=curr;
for(i=maxp-1;i>=0;i--)
if(k>=(1<<i)){
k-=(1<<i);
ans=lift[ans][i];
}
// cout<<ans<<endl;
return trie[ans].c;
}
