#include<bits/stdc++.h>
using namespace std;
int st = 0, co = 1, a[1000005], depth[1000005], ch[1000005], trie[1000005][26], succ[1000005][20];
void Init() {};
void initsucc(int i) {
for (int j = 1; j < 20; j++) {
succ[i][j] = succ[succ[i][j-1]][j-1];
}
}
int kthjump(int a, int k) {
for (int i = 0; i < 20; i++) {
if (k & (1 << i)) {
a = succ[a][i];
}
}
return a;
}
void TypeLetter(char l) {
int n = a[st], c = l-'a';
st++;
if (!trie[n][c]) {
succ[co][0] = n;
depth[co] = depth[n]+1;
trie[n][c] = co;
ch[co] = c;
initsucc(co);
co++;
}
a[st] = trie[n][c];
}
void UndoCommands(int U) {
st++;
a[st] = a[st-1-U];
}
char GetLetter(int P) {
int n = a[st];
int a = kthjump(n, depth[n]-1-P);
return (char)(ch[a]+'a');
}
