#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int K = 22;
int num_commands;
int depth[MAXN];
int tree_node[MAXN];
char tree_letter[MAXN];
int cur_node;
int num_nodes;
int dp[K][MAXN];
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;
dp[0][num_nodes] = cur_node;
for (int j = 1; j < K; j++) {
dp[j][num_nodes] = dp[j - 1][dp[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 = K - 1; j >= 0; j--) {
int cand = dp[j][ans_node];
if (depth[cand] > P) ans_node = cand;
}
return tree_letter[ans_node];
}
// void PrintAll() {
// cout << "FULL WORD: ";
// for (int i = 0; i < depth[cur_node]; i++) {
// cout << GetLetter(i);
// }
// cout << endl;
// }
