#include <bits/stdc++.h>
using namespace std;
#ifndef wambule
// #include "scrivener.h"
#else
#endif
const int N = 1000006;
const int L = 21;
struct ovo {
vector<ovo*> v;
ovo *up[L];
int dt;
char c;
ovo() {}
ovo(ovo *op, char _c) {
c = _c;
dt = op->dt + 1;
v.clear();
up[0] = op;
for(int i = 1; i < L; ++i) {
up[i] = up[i - 1];
if(up[i] != NULL) up[i] = up[i]->up[i];
}
}
ovo* A(char c) {
v.push_back(new ovo(this, c));
return *(--v.end());
}
} rt, *dg;
vector<ovo*> v;
void Init() {
rt.c = ' ';
rt.dt = -1;
rt.v.clear();
for(int i = 0; i < L; ++i) {
rt.up[i] = NULL;
}
dg = &rt;
}
void TypeLetter(char c) {
dg = dg->A(c);
v.push_back(dg);
}
void UndoCommands(int x) {
dg = v[(int)v.size() - 1 - x];
v.push_back(dg);
}
char GetLetter(int id) {
ovo *x = dg;
for(int i = L - 1; i >= 0; --i) {
if(x->up[i] != NULL && x->up[i]->dt >= id) {
x = x->up[i];
}
}
#ifdef wambule
cout << x->c << endl;
#endif
return x->c;
}
#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
