#include <iostream>
using namespace std;
const int N = 1<<20;
int cur, tot, Sz[N], Par[N][20], Lst[N];
char chr[N];
void Init(){
}
void print(int id){
if (id == 0){
cout<<"print : ";
return;
}
print(Par[id][0]);
cout<<chr[id]<<' ';
}
void TypeLetter(char c){
int nw = ++tot;
Lst[nw] = nw;
chr[nw] = c;
Par[nw][0] = Lst[cur];
Sz[nw] = Sz[Lst[cur]] + 1;
for (int i=1;i<20;i++)
Par[nw][i] = Par[Par[nw][i-1]][i-1];
cur = nw;
// print(Lst[cur]);
// cout<<endl;
}
void UndoCommands(int u){
int nw = ++tot;
Lst[nw] = Lst[cur - u];
cur = nw;
// print(Lst[cur]);
// cout<<endl;
}
char GetLetter(int P){
P++;
int now = Lst[cur];
int k = Sz[now] - P;
for (int i=0;i<20;i++)
if ((1<<i) & k)
now = Par[now][i];
return chr[now];
}
