#include <bits/stdc++.h>
char last;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
struct x{
char letra;
lli padre;
};
lli p,act,cont = 1;
x instruccion[1000002];
lli binaryUp[1000002][22];
void Init() {}
void TypeLetter(char L) {
instruccion[cont].letra = L;
instruccion[cont].padre = cont-1;
p = 0;
binaryUp[cont][0] = cont-1;
while (binaryUp [ binaryUp[cont][p] ][p] > 0) {
binaryUp[cont][p+1] = binaryUp [ binaryUp[cont][p] ][p];
p++;
}
cont++;
}
void UndoCommands(int U) {
instruccion[cont] = instruccion[cont - U - 1];
cont++;
}
char GetLetter(int P) {
p = 0;
act = cont-1;
while (P > 0) {
if (P%2 == 1) act = binaryUp[act][p];
P /= 2;
p++;
}
return instruccion[act].letra;
}
