static constexpr int MAX_CALLS = 1000000 + 5;
static constexpr int LOG = 21;
static int parent_jump[MAX_CALLS][LOG];
static int text_length[MAX_CALLS];
static char letter_value[MAX_CALLS];
static int command_root[MAX_CALLS];
static int node_count;
static int command_count;
static int current_root;
void Init() {
node_count = 0;
command_count = 0;
current_root = 0;
command_root[0] = 0;
text_length[0] = 0;
}
void TypeLetter(char L) {
++node_count;
letter_value[node_count] = L;
text_length[node_count] = text_length[current_root] + 1;
parent_jump[node_count][0] = current_root;
for (int i = 1; i < LOG; ++i) {
parent_jump[node_count][i] = parent_jump[parent_jump[node_count][i - 1]][i - 1];
}
current_root = node_count;
command_root[++command_count] = current_root;
}
void UndoCommands(int U) {
current_root = command_root[command_count - U];
command_root[++command_count] = current_root;
}
char GetLetter(int P) {
int node = current_root;
int steps = text_length[node] - 1 - P;
for (int i = 0; i < LOG; ++i) {
if (steps & (1 << i)) {
node = parent_jump[node][i];
}
}
return letter_value[node];
}
