#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 11;
struct Node{
char c;
int nxt[26] = {};
int lift[20] = {};
int pos = -1;
} t[MAXN];
int trie_id = 0;
int extend(int v, char c){
if(!t[v].nxt[c - 'a']) t[v].nxt[c - 'a'] = trie_id++;
int u = t[v].nxt[c - 'a'];
t[u].c = c; t[u].lift[0] = v; t[u].pos = t[v].pos + 1;
for(int j = 1; j < 20; j++) t[u].lift[j] = t[t[u].lift[j - 1]].lift[j - 1];
return u;
}
int root[MAXN], id = 0;
void Init() {
root[0] = 0; trie_id++;
}
void TypeLetter(char L) {
++id; root[id] = extend(root[id - 1], L);
}
void UndoCommands(int U) {
++id; root[id] = root[id - U - 1];
}
char GetLetter(int P) {
int v = root[id];
for(int j = 19; j >= 0; j--){
if(t[v].pos - P >= (1 << j)){
v = t[v].lift[j];
}
}
return t[v].c;
}
