#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
const int N = (int) 1e6 + 10;
char node[N];
int trie[N][26];
int pv[N][20];
int depth[N];
int lg[N];
int id;
int sz;
void Init() {
node[0] = '!';
memset(trie, -1, sizeof(trie));
id = 1;
sz = 1;
}
void TypeLetter(char ll) {
int v = lg[id - 1];
int l = ll - 'a';
if (trie[v][l] != -1) {
lg[id] = trie[v][l];
id++;
return;
}
int to = sz;
trie[v][l] = to;
depth[to] = depth[v] + 1;
lg[id] = to;
pv[to][0] = v;
for (int i = 1; i < 20; i++) {
pv[to][i] = pv[pv[to][i - 1]][i - 1];
}
node[to] = ll;
id++;
sz++;
}
void UndoCommands(int u) {
lg[id] = lg[id - 1 - u];
id++;
}
char GetLetter(int p) {
int v = lg[id - 1];
int up = depth[v] - 1 - p;
for (int i = 19; i >= 0; i--) {
if (up & (1 << i)) {
v = pv[v][i];
}
}
return node[v];
}
#ifdef tabr
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Init();
TypeLetter('a');
TypeLetter('b');
cout << GetLetter(1) << '\n';
TypeLetter('d');
UndoCommands(2);
UndoCommands(1);
cout << GetLetter(2) << '\n';
TypeLetter('e');
UndoCommands(1);
UndoCommands(5);
TypeLetter('c');
cout << GetLetter(2) << '\n';
UndoCommands(2);
cout << GetLetter(2) << '\n';
return 0;
}
#endif
