#include <bits/stdc++.h>
using namespace std;
const int maxN = 1e6 + 20;
const int maxK = 20;
int par[maxN][maxK];
char a[maxN];
int id[maxN];
int depth[maxN];
int op;
int node;
void Init() {
op = 1;
node = 1;
id[op] = 1;
depth[node] = 0;
for (int k = 0; k < maxK; k++) {
par[1][k] = 1;
}
}
void TypeLetter(char L) {
op++;
node++;
par[node][0] = id[op - 1];
depth[node] = depth[id[op - 1]] + 1;
a[node] = L;
for (int k = 1; k < maxK; k++) {
par[node][k] = par[par[node][k - 1]][k - 1];
}
id[op] = node;
}
void UndoCommands(int U) {
op++;
id[op] = id[op - 1 - U];
}
char GetLetter(int P) {
P++;
int u = id[op];
int h = depth[u] - P;
for (int k = 0; k < maxK; k++) {
if ((h >> k) & 1) {
u = par[u][k];
}
}
return a[u];
}
