#include<bits/stdc++.h>
using namespace std;
int loc[1000005];
struct node{
int dep;
char curr;
int up;
int par[25];
unordered_map<char, int> ch;
};
node trie[1000005];
int cnt = 1;
int step = 0;
void Init() {
loc[0] = 0;
for(int i = 0; i < 1000000; i++) for(int j = 0; j < 25; j++) trie[i].par[j] = i;
return;
}
void TypeLetter(char L) {
step++;
int lst = loc[step - 1];
if(trie[lst].ch[L] == 0) {
trie[lst].ch[L] = cnt;
trie[cnt].dep = trie[lst].dep + 1;
trie[cnt].curr = L;
trie[cnt].par[0] = lst;
for(int i = 1; i < 25; i++) {
trie[cnt].par[i] = trie[trie[cnt].par[i - 1]].par[i - 1];
}
cnt++;
}
loc[step] = trie[lst].ch[L];
}
void UndoCommands(int U) {
step++;
loc[step] = loc[step - U - 1];
}
char GetLetter(int p) {
p++;
int dif = trie[loc[step]].dep - p;
int pt = loc[step], hm = 0;
while(dif) {
if(dif & (1 << hm)) {
pt = trie[pt].par[hm];
dif -= (1 << hm);
}
hm++;
}
return trie[pt].curr;
}
