#include <bits/stdc++.h>
using namespace std;
char last;
vector <char> t;
int cur = 0;
int up[22][1000005];
int d[1000005];
int node[1000005];
int curnode;
void Init() {}
void TypeLetter(char L) {
cur++;
int prev = node[cur-1];
curnode++;
up[curnode][0] = prev;
t.emplace_back(L);
d[curnode] = d[prev] + 1;
for (int i = 1; i <= 20; i++) {
up[curnode][i] = up[up[curnode][i-1]][i-1];
}
node[cur] = curnode;
}
void UndoCommands(int U) {
cur++;
node[cur] = node[cur - U - 1];
}
char GetLetter(int P) {
int now = node[cur];
P = d[now]-P-1;
for (int i = 20; i >= 0; i--) {
if (P >= (1<<i)) {
cur = up[now][i];
P -= (1<<i);
}
}
return t[now];
}
