#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
// #include ".h"
#else
#endif
const int N = 1000006;
const int L = 21;
int dg;
// in loving memory of the deceased structure
vector<pair<pair<char, int>, vector<int>>> ilm;
vector<int> v;
void Init() {
dg = 0;
ilm.clear();
ilm.push_back({{' ', -1}, vector<int>(L, -1)});
}
void TypeLetter(char c) {
int x = ilm.size();
ilm.push_back({{c, ilm[dg].first.second + 1}, vector<int>(L, -1)});
ilm[x].second[0] = dg;
for(int i = 1; i < L; ++i) {
ilm[x].second[i] = ilm[x].second[i - 1];
if(ilm[x].second[i] != -1) ilm[x].second[i] = ilm[ilm[x].second[i]].second[i - 1];
}
dg = x;
v.push_back(dg);
}
void UndoCommands(int x) {
dg = v[(int)v.size() - 1 - x];
v.push_back(dg);
}
char GetLetter(int id) {
int x = dg;
for(int i = L - 1; i >= 0; --i) {
if(ilm[x].second[i] != -1 && ilm[ilm[x].second[i]].first.second >= id) {
x = ilm[x].second[i];
}
}
#ifdef wambule
cout << "[:] " << ilm[x].first.first << endl;
#endif
return ilm[x].first.first;
}
#ifdef wambule
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
Init();
TypeLetter('a');
TypeLetter('b');
GetLetter(1);
TypeLetter('d');
UndoCommands(2);
UndoCommands(1);
GetLetter(2);
TypeLetter('e');
UndoCommands(1);
UndoCommands(5);
TypeLetter('c');
GetLetter(2);
UndoCommands(2);
GetLetter(2);
return 0;
}
#endif
