#include <bits/stdc++.h>
using namespace std;
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("-Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#ifndef wambule
// #include ".h"
#else
#endif
const int N = 1000006;
const int L = 20;
int dg;
int wz;
char c[N];
int dt[N];
int up[N][L];
int vs;
int v[N];
void Init() {
vs = 0;
wz = 1;
dg = 0;
dt[0] = -1;
c[0] = ' ';
for(int i = 0; i < L; ++i) {
up[0][i] = -1;
}
}
void TypeLetter(char _c) {
c[wz] = _c;
dt[wz] = dt[dg] + 1;
up[wz][0] = dg;
for(int i = 1; i < L; ++i) {
up[wz][i] = up[wz][i - 1];
if(up[wz][i] ^ -1) up[wz][i] = up[up[wz][i]][i - 1];
}
dg = wz;
++wz;
v[vs++] = dg;
}
void UndoCommands(int x) {
dg = v[vs - 1 - x];
v[vs++] = dg;
}
char GetLetter(int id) {
int x = dg, y = 0;
for(int i = L - 1; i >= 0; --i) {
y = up[x][i];
if(y != -1 && dt[y] >= id) {
x = y;
}
}
#ifdef wambule
cout << "[:] " << c[x] << endl;
#endif
return c[x];
}
#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
