namespace {
constexpr int MAX_CALLS = 1000000 + 5;
constexpr int LOG = 20;
int up[MAX_CALLS][LOG];
int depthArr[MAX_CALLS];
char valueArr[MAX_CALLS];
int historyRoot[MAX_CALLS];
int nodeCount;
int commandCount;
int currentRoot;
}
void Init() {
nodeCount = 0;
commandCount = 0;
currentRoot = 0;
historyRoot[0] = 0;
depthArr[0] = 0;
valueArr[0] = '\0';
for (int i = 0; i < LOG; ++i) up[0][i] = 0;
}
void TypeLetter(char L) {
int v = ++nodeCount;
valueArr[v] = L;
depthArr[v] = depthArr[currentRoot] + 1;
up[v][0] = currentRoot;
for (int i = 1; i < LOG; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
currentRoot = v;
historyRoot[++commandCount] = currentRoot;
}
void UndoCommands(int U) {
currentRoot = historyRoot[commandCount - U];
historyRoot[++commandCount] = currentRoot;
}
char GetLetter(int P) {
int v = currentRoot;
int steps = depthArr[v] - 1 - P;
for (int i = 0; i < LOG; ++i) {
if (steps & (1 << i)) {
v = up[v][i];
}
}
return valueArr[v];
}
