#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 6;
char C[N];
int Tries, idx, Nowidx, D[N], dep[N], T[N][37], P[N][21];
void Init() {
Tries = 1;
Nowidx = 1;
D[0] = Nowidx;
dep[Nowidx] = 0;
}
void TypeLetter(char c) {
++idx;
int t = c - 'a';
if (!T[Nowidx][t]) {
T[Nowidx][t] = ++Tries;
C[Tries] = c;
dep[T[Nowidx][t]] = dep[Nowidx] + 1;
P[T[Nowidx][t]][0] = Nowidx;
for (int j = 1; j <= 20; ++j)
P[T[Nowidx][t]][j] = P[P[T[Nowidx][t]][j - 1]][j - 1];
}
D[idx] = T[Nowidx][t];
Nowidx = D[idx];
}
void UndoCommands(int x) {
++idx;
D[idx] = D[idx - x - 1];
Nowidx = D[idx];
}
char GetLetter(int x) {
++x;
int Nq = Nowidx;
if (dep[Nq] == x) return C[Nq];
for (int i = 20; i >= 0; --i) {
if (dep[P[Nq][i]] > x) Nq = P[Nq][i];
}
Nq = P[Nq][0];
return C[Nq];
}
