#include <array>
#include <vector>
namespace {
constexpr int MAX_OPS = 1000000;
constexpr int LOG = 21;
std::vector<std::array<int, LOG>> up;
std::vector<int> depth;
std::vector<char> value;
std::vector<int> versionRoot;
int currentRoot = 0;
}
void Init() {
up.clear();
depth.clear();
value.clear();
versionRoot.clear();
up.reserve(MAX_OPS + 1);
depth.reserve(MAX_OPS + 1);
value.reserve(MAX_OPS + 1);
versionRoot.reserve(MAX_OPS + 1);
up.push_back({});
depth.push_back(0);
value.push_back('\0');
versionRoot.push_back(0);
currentRoot = 0;
}
void TypeLetter(char L) {
int node = static_cast<int>(up.size());
up.push_back({});
depth.push_back(depth[currentRoot] + 1);
value.push_back(L);
up[node][0] = currentRoot;
for (int j = 1; j < LOG; ++j) {
up[node][j] = up[up[node][j - 1]][j - 1];
}
currentRoot = node;
versionRoot.push_back(currentRoot);
}
void UndoCommands(int U) {
int commandCount = static_cast<int>(versionRoot.size()) - 1;
currentRoot = versionRoot[commandCount - U];
versionRoot.push_back(currentRoot);
}
char GetLetter(int P) {
int node = currentRoot;
int targetDepth = P + 1;
int diff = depth[node] - targetDepth;
for (int j = 0; j < LOG; ++j) {
if (diff & (1 << j)) {
node = up[node][j];
}
}
return value[node];
}
