#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
vector<int> ans;
int trie[1000001][26], depth[1000001], p[1000001][21], inc;
char letter[1000001];
void Init(){
inc = 0;
memset(p,-1,sizeof p);
ans.push_back(0);
}
void TypeLetter(char L){
int cur = ans[ans.size()-1], ch = L-'a';
if (!trie[cur][ch]) {
trie[cur][ch] = ++inc;
depth[inc] = depth[cur] + 1;
p[inc][0] = cur;
for (int x = 1; x <= LOG; x++)
if (~p[inc][x-1])
p[inc][x] = p[p[inc][x-1]][x-1];
letter[inc] = L;
}
ans.push_back(trie[cur][ch]);
}
void UndoCommands(int U){
ans.push_back(ans[ans.size()-1-U]);
}
char GetLetter(int P){
int cur = ans.back(); P++;
for (int x = LOG; x >= 0; x--)
if (~p[cur][x] && depth[p[cur][x]] >= P)
cur = p[cur][x];
return letter[cur];
}
