#include <bits/stdc++.h>
#define N 1000005
#define K 21
using namespace std;
struct node{
int par,cnt;
node(){
par = cnt = 0;
}
};
node sp[N][K];
char last[N];
int cnt = 0;
void Init() {}
void TypeLetter(char l) {
last[cnt+1] = l;
sp[cnt+1][0].par = cnt;
sp[cnt+1][0].cnt = 1;
cnt++;
for(int j = 1;j<K;j++){
sp[cnt][j].par = sp[sp[cnt][j-1].par][j-1].par;
sp[cnt][j].cnt = sp[cnt][j-1].cnt + sp[sp[cnt][j-1].par][j-1].cnt;
}
}
void UndoCommands(int u) {
sp[cnt+1][0].par = cnt - u;
sp[cnt+1][0].cnt = 0;
cnt++;
for(int j = 1;j<K;j++){
sp[cnt][j].par = sp[sp[cnt][j-1].par][j-1].par;
sp[cnt][j].cnt = sp[cnt][j-1].cnt + sp[sp[cnt][j-1].par][j-1].cnt;
}
}
char GetLetter(int p) {
int tot = sp[cnt][K-1].cnt;
int needed = tot - p;
int tmp = cnt;
for(int i = K-1;i>=0;i--){
if(sp[tmp][i].cnt < needed){
needed -= sp[tmp][i].cnt;
tmp = sp[tmp][i].par;
}
}
return last[tmp];
}
