#include <bits/stdc++.h>
using namespace std;
int num_commands;
int depth[1000005];
int tree_node[1000005];
char tree_letter[1000005];
int cur_node;
int num_nodes;
int jump[22][1000005];
void Init() {
cur_node = 0;
num_nodes = 0;
}
void TypeLetter(char L) {
num_nodes++;
tree_letter[num_nodes] = L;
depth[num_nodes] = depth[cur_node] + 1;
num_commands++;
tree_node[num_commands] = num_nodes;
jump[0][num_nodes] = cur_node;
for (int j = 1; j < 22; j++) {
jump[j][num_nodes] = jump[j - 1][jump[j - 1][num_nodes]];
}
cur_node = tree_node[num_commands];
}
void UndoCommands(int U) {
num_commands++;
tree_node[num_commands] = tree_node[num_commands - U - 1];
cur_node = tree_node[num_commands];
}
char GetLetter(int P) {
int ans_node = cur_node;
for (int j = 21; j >= 0; j--) {
int cand = jump[j][ans_node];
if (depth[cand] > P) {
ans_node = cand;
}
}
return tree_letter[ans_node];
}
