#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=1e6+1;
int cur, up[N][21];
vector<char> trie;
vector<vector<int> > nxt;
vector<int> len, step;
void Init() {
cur=0;
trie.clear();
nxt.clear();
len.clear();
trie.push_back('!');
nxt.push_back(vector<int>(26, -1));
len.push_back(0);
for (int i=0; i<=20; i++) up[0][i]=-1;
step.clear();
step.push_back(cur);
}
void TypeLetter(char L) {
if (nxt[cur][L-'a']==-1){
trie.push_back(L);
nxt.push_back(vector<int>(26, -1));
nxt[cur][L-'a']=trie.size()-1;
len.push_back(len[cur]+1);
up[trie.size()-1][0]=cur;
for (int i=1; i<=20; i++){
up[trie.size()-1][i]=(up[trie.size()-1][i-1]==-1? -1: up[up[trie.size()-1][i-1]][i-1]);
}
}
cur=nxt[cur][L-'a'];
step.push_back(cur);
}
void UndoCommands(int U) {
cur=step[step.size()-U-1];
step.push_back(cur);
}
char GetLetter(int P) {
P=len[cur]-P-1;
int t=cur;
for (int i=20; i>=0; i--){
if (P>=(1<<i)){
P-=(1<<i);
t=up[t][i];
}
}
return trie[t];
}
