#include <vector>
#include <string>
using namespace std;
#define pb push_back
const int lg = 20;
struct node{
char val;
int idx;
vector<node*> pr;
node(char c){
val = c;
idx = 0;
pr.resize(lg);
pr.assign(lg, nullptr);
}
};
//vector<node*> v;
vector<int> idx;
vector<char> val;
vector<vector<int>> pr;
vector<int> v;
int k = 1;
void Init() {
v.pb(0);
idx.pb(-1);
val.pb(' ');
pr.pb(vector<int>(lg, -1));
}
void TypeLetter(char l) {
int prev = v.back();
v.pb(k++);
idx.pb(idx[prev] + 1);
val.pb(l);
pr.pb(vector<int>(lg));
if (prev == 0) prev = -1;
pr.back()[0] = prev;
for (int i = 1; i < lg; ++i){
if (pr.back()[i-1] == -1) break;
pr.back()[i] = pr[pr.back()[i-1]][i-1];
}
}
void UndoCommands(int u) {
int n = v.size();
int cur = v[n - u - 1];
v.pb(cur);
}
char GetLetter(int p) {
int cur = v.back();
for (int i = lg - 1; i >= 0; --i){
if (pr[cur][i] != -1 && idx[pr[cur][i]] >= p){
cur = pr[cur][i];
}
}
return val[cur];
}
