#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e6 + 15;
const int ALP = 26;
int trie[MAX][ALP], pai[MAX], cur, node;
char letter[MAX];
vector<int> states;
void Init() {}
void TypeLetter(char L) {
int id = L - 'a';
if(trie[cur][id] == 0){
trie[cur][id] = ++node;
pai[node] = cur;
}
cur = trie[cur][id];
letter[cur] = L;
states.emplace_back(cur);
}
void UndoCommands(int U) {
while(U-- && states.size())
states.pop_back();
cur = states.back();
}
char GetLetter(int P) {
int aux = cur;
string resp = "";
while(aux != 0){
resp += letter[aux];
aux = pai[aux];
}
return resp[P];
}
