#include "bits/stdc++.h"
using namespace std;
const int N = 2e6+6;
const int LOG = 21;
int nd,h,a[N][LOG],lvl[N];
vector <int> v;
char c[N];
void Init() {}
char get(int x){
int l = h;
for (int i = LOG-1;i >= 0;i--){
if (x>=(1<<i))
l = a[l][i],x-=(1<<i);
}
return c[l];
}
void TypeLetter(char l) {
int u = nd+1;
nd++;
c[u] = l;
a[u][0] = h;
lvl[u] = lvl[h]+1;
h = nd;
for (int i = 1;i < LOG;i++){
if (a[h][i-1])
a[h][i] = a[a[h][i-1]][i-1];
}
v.push_back(h);
}
void UndoCommands(int U) {
h = v[v.size()-U-1];
v.push_back(h);
}
char GetLetter(int P) {
return get(lvl[h]-P-1);
}
