#include <bits/stdc++.h>
using namespace std;
vector<char> c;
vector<int> dep, ptr;
vector<vector<int>> pa, ch;
void Init() {
c.push_back('.');
dep.push_back(0);
ptr.push_back(0);
pa.emplace_back(20, 0);
ch.emplace_back(26, -1);
}
void TypeLetter(char L) {
int y = L - 'a', x = ptr.back();
if (ch[x][y] == -1) {
int i = ch[x][y] = c.size();
c.push_back(L);
dep.push_back(dep[x] + 1);
pa.emplace_back(20);
ch.emplace_back(26, -1);
pa[i][0] = x;
for (int j = 1; j < 20; ++j)
pa[i][j] = pa[pa[i][j - 1]][j - 1];
}
ptr.push_back(ch[x][y]);
}
void UndoCommands(int U) {
int i = ptr.size() - 1 - U;
ptr.push_back(ptr[i]);
}
char GetLetter(int P) {
++P;
int i = ptr.back();
for (int j = 19; ~j; --j)
if (dep[pa[i][j]] >= P)
i = pa[i][j];
return c[i];
}
