#include <bits/stdc++.h>
using namespace std;
struct Node {
char ch;
int depth;
vector<int> ancestors;
};
vector<Node> buffer;
vector<int> state;
void Init() {
;
}
int findAncestor(int idx, int target_depth) {
int delta = buffer[idx].depth - target_depth;
int step = 0;
while (delta > 0) {
++step;
delta /= 2;
}
return (buffer[idx].depth == target_depth)
? idx
: findAncestor(buffer[idx].ancestors[step - 1], target_depth);
}
void TypeLetter(char c) {
if (state.empty() || state.back() == -1) {
buffer.push_back({c, 0, {}});
} else {
int parent = state.back();
int new_depth = buffer[parent].depth + 1;
vector<int> links;
links.push_back(parent);
while (links.size() < buffer[parent].ancestors.size() + 1) {
parent = buffer[parent].ancestors[links.size() - 1];
links.push_back(parent);
}
buffer.push_back({c, new_depth, links});
}
state.push_back((int)buffer.size() - 1);
}
void UndoCommands(int k) {
if (k == state.size()) {
state.push_back(-1);
} else {
int restored = state[state.size() - 1 - k];
state.push_back(restored);
}
}
char GetLetter(int pos) {
int idx = findAncestor(state.back(), pos);
return buffer[idx].ch;
}
