#include <cstdio>
#define debug(...) //fprintf(stderr, __VA_ARGS__)
using namespace std;
const int LOG = 20;
const int N = 1 << LOG;
char c[N];
int pos[N], lst, nov = 1, up[N][LOG], dep[N];
char climb(int u, int x) {
for(int i = LOG - 1; i >= 0; --i) {
if(x & (1 << i)) {
u = up[u][i];
}
}
return c[u];
}
void Init() {}
void TypeLetter(char L) {
up[nov][0] = pos[lst];
for(int i = 1; i < LOG; ++i) {
up[nov][i] = up[up[nov][i - 1]][i - 1];
}
dep[nov] = dep[pos[lst]] + 1;
c[nov] = L;
pos[++lst] = nov++;
}
void UndoCommands(int U) {
++lst;
pos[lst] = pos[lst - U - 1];
}
char GetLetter(int P) {
return climb(pos[lst], dep[pos[lst]] - P - 1);
}
