#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
string node;
vector<vector<int>> trie;
vector<vector<int>> pv;
vector<int> depth;
vector<int> lg;
void Init() {
node += "!";
trie.emplace_back(vector<int>(26, -1));
pv.emplace_back(vector<int>(20, 0));
depth.emplace_back(0);
lg.emplace_back(0);
}
void TypeLetter(char ll) {
int v = lg.back();
int l = ll - 'a';
if (trie[v][l] != -1) {
lg.emplace_back(trie[v][l]);
return;
}
int to = (int) node.size();
trie[v][l] = to;
trie.emplace_back(vector<int>(26, -1));
pv.emplace_back(vector<int>(20, 0));
depth.emplace_back(depth[v] + 1);
lg.emplace_back(to);
pv[to][0] = v;
for (int i = 1; i < 20; i++) {
pv[to][i] = pv[pv[to][i - 1]][i - 1];
}
node += ll;
}
void UndoCommands(int u) {
lg.emplace_back(lg.rbegin()[u]);
}
char GetLetter(int p) {
int v = lg.back();
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
