#include <vector>
using namespace std;
const int MAXN = 1000005;
const int LOGN = 20;
int parent[MAXN][LOGN];
char node_char[MAXN];
int depth[MAXN];
int last_node[MAXN];
int cmd_count = 0;
int nodes_cnt = 0;
void Init() {
nodes_cnt = 0;
cmd_count = 0;
depth[0] = 0;
for (int i = 0; i < LOGN; i++) parent[0][i] = 0;
}
void TypeLetter(char L) {
cmd_count++;
int prev_node = last_node[cmd_count - 1];
nodes_cnt++;
node_char[nodes_cnt] = L;
depth[nodes_cnt] = depth[prev_node] + 1;
parent[nodes_cnt][0] = prev_node;
for (int i = 1; i < LOGN; i++) {
parent[nodes_cnt][i] = parent[parent[nodes_cnt][i - 1]][i - 1];
}
last_node[cmd_count] = nodes_cnt;
}
void UndoCommands(int U) {
int target_cmd = cmd_count - U;
cmd_count++;
last_node[cmd_count] = last_node[target_cmd];
}
char GetLetter(int P) {
int curr = last_node[cmd_count];
int dist = depth[curr] - (P + 1);
for (int i = LOGN - 1; i >= 0; i--) {
if (dist >= (1 << i)) {
curr = parent[curr][i];
dist -= (1 << i);
}
}
return node_char[curr];
}
