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