#include <bits/stdc++.h>
using namespace std;
char last;
const int LOG = 20;
const int N = 1e6 + 6;
int idd;
char c[N];
int sz[N];
int p[LOG][N];
vector<int> ids;
void Init() {
idd = 2;
ids.push_back(1);
}
void TypeLetter(char L) {
int curId = idd++;
int prnt = ids.back();
p[0][curId] = prnt;
for (int j = 1; j < LOG; ++j) {
p[j][curId] = p[j - 1][p[j - 1][curId]];
}
c[curId] = L;
sz[curId] = sz[prnt] + 1;
ids.push_back(curId);
}
void UndoCommands(int U) {
int newId = ids[ids.size() - 1 - U];
ids.push_back(newId);
}
char GetLetter(int P) {
int v = ids.back();
for (int j = LOG - 1; j >= 0; --j) {
if (p[j][v] && sz[p[j][v]] > P) {
v = p[j][v];
}
}
return c[v];
}
