# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
const int N = 1e6 + 5;
char ch[N];
int par[N][20], op = 0, cnt = 0, cur = 0,vert[N],lvl[N], trie[N][27];
void Init() {
for (int i = 1; i < N; i++) {
for (int j = 0; j <= 19; j++) {
par[i][j] = -1;
}
}
}
void TypeLetter(char L) {
op++;
if (trie[cur][L - 'a']) {
cur = trie[cur][L - 'a'];
vert[op] = cur;
ch[cur] = L;
} else {
trie[cur][L - 'a'] = ++cnt;
par[cnt][0] = cur;
for (int i = 1; i <= 19; i++) {
if (par[cnt][i - 1] != -1) {
par[cnt][i] = par[par[cnt][i - 1]][i - 1];
}
}
vert[op] = cnt;
lvl[cnt] = lvl[cur] + 1;
cur = cnt;
ch[cur] = L;
}
}
void UndoCommands(int U) {
vert[op + 1] = cur = vert[op - U];
op++;
}
char GetLetter(int P) {
int pos = cur;
P++;
for (int i = 19; i >= 0; i--) {
if (par[pos][i] != -1 && lvl[par[pos][i]] >= P) {
pos = par[pos][i];
}
}
return ch[pos];
}
