#include <bits/stdc++.h>
template <class T>
using Vec = std::vector<T>;
struct Node {
char written;
int depth;
std::array<int, 20> parent;
};
Vec<int> at;
Vec<Node> node;
void Init() {
at.push_back(0);
std::array<int, 20> tmp;
tmp.fill(0);
node.push_back(Node{'$', 0, tmp});
}
void TypeLetter(char L) {
std::array<int, 20> tmp;
tmp[0] = at.back();
for (int i = 1; i < 20; ++i) {
tmp[i] = node[tmp[i - 1]].parent[i - 1];
}
node.push_back(Node{L, node[at.back()].depth + 1, tmp});
at.push_back(node.size() - 1);
}
void UndoCommands(int U) {
at.push_back(at[at.size() - U - 1]);
}
char GetLetter(int P) {
int u = at.back();
int len = node[u].depth - P - 1;
for (int i = 0; i < 20; ++i) {
if (len >> i & 1) {
u = node[u].parent[i];
}
}
return node[u].written;
}
