#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
const int N = 1000000;
int p[N], depth[N], to[N];
int up[N][LOG];
char letter[N];
int cnt, last;
void create(int x) {
up[x][0] = p[x];
for (int i = 1; i < LOG; i++) {
up[x][i] = up[up[x][i-1]][i-1];
}
}
void Init() {
cin.tie(0);
ios::sync_with_stdio(false);
cnt = 0;
last = 0;
depth[0] = -1;
}
void TypeLetter(char L) {
to[cnt] = cnt;
p[cnt] = last;
depth[cnt] = depth[last] + 1;
create(cnt);
letter[cnt] = L;
last = cnt;
cnt++;
}
void UndoCommands(int U) {
to[cnt] = to[cnt - U - 1];
last = to[cnt];
cnt++;
}
char GetLetter(int P) {
int distance = depth[last] - P, x = last;
for (int i = LOG; i >= 0; i--) {
if (distance & (1<<i)) x = up[x][i];
}
return letter[x];
}
