//#include "grader.h"
#include <bits/stdc++.h>
char last;
struct node{
char c;
node *pr[23];
int deep;
node(){
for (int i = 0; i <= 21; i++)
pr[i] = nullptr;
deep = 0;
}
};
node* bor[1000100];
int cnt;
void Init(){
cnt = 0;
bor[0] = new node();
}
void TypeLetter(char L) {
++cnt;
if (!bor[cnt])
bor[cnt] = new node();
bor[cnt]->c = L;
bor[cnt]->pr[0] = bor[cnt-1];
for (int i = 1; i <= 21; i++){
bor[cnt]->pr[i] = (bor[cnt]->pr[i - 1] ? bor[cnt]->pr[i - 1]->pr[i - 1] : nullptr);
}
bor[cnt]->deep = bor[cnt-1]->deep+1;
}
void UndoCommands(int U) {
++cnt;
bor[cnt] = bor[cnt-U-1];
}
char GetLetter(int P) {
node* ver = bor[cnt];
int h = ver->deep-P-1;
for (int i = 21; i >= 0; i--){
if (h - (1<<i) >= 0){
h -= (1<<i);
ver = ver->pr[i];
}
}
return ver->c;
}
