#include <bits/stdc++.h>
using namespace std;
char last;
const int LOG = 22;
const int N = (int)1e6 + 50;
struct Trie{
char value;
Trie *nex[22];
int siz;
Trie(){
value = '!';
for(int i = 0; i < 22;i ++ ){
nex[i] = NULL;
}
siz = 0;
}
};
Trie *Q[N];
int cnt;
void Init() {
Q[0] = new Trie();
}
void TypeLetter(char L) {
++ cnt;
Q[cnt] = new Trie();
Q[cnt] -> nex[0] = Q[cnt - 1];
for(int i = 1; i < LOG; i ++ ){
if(Q[cnt] -> nex[i - 1] != NULL){
Q[cnt] -> nex[i] = Q[cnt] -> nex[i - 1] -> nex[i - 1];
}
}
Q[cnt] -> value = L;
Q[cnt] -> siz = Q[cnt] -> nex[0] -> siz + 1;
}
void UndoCommands(int U) {
++ cnt;
Q[cnt] = Q[cnt - U - 1];
}
char GetLetter(int P) {
int dep = Q[cnt] -> siz;
dep = dep - 1 - P;
Trie *T = Q[cnt];
for(int i = 0;i < LOG;i ++ ){
if(dep & (1 << i)){
T = T -> nex[i];
}
}
return T -> value;
}
