#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
const int N = 1e6 + 5;
vector<int> ancetres[N];
int prof[N];
char lettre[N];
int nNoeuds = 0, noeudCur = 0;
void Init() {
prof[0] = 0;
nNoeuds = 1;
}
void TypeLetter(char L) {
int pere = noeudCur;
noeudCur = nNoeuds++;
prof[noeudCur] = prof[pere] + 1;
lettre[noeudCur] = L;
ancetres[noeudCur].pb(pere);
for (int ind = 0; ind < sz(ancetres[ancetres[noeudCur][ind]]); ++ind)
ancetres[noeudCur].pb(ancetres[ancetres[noeudCur][ind]][ind]);
}
void UndoCommands(int U) {
noeudCur -= U + 1;
}
char GetLetter(int P) {
int noeud = noeudCur;
for (int i = sz(ancetres[noeud]) - 1; i >= 0; --i){
if (i < sz(ancetres[noeud]) && prof[ancetres[noeud][i]] > P)
noeud = ancetres[noeud][i];
}
return lettre[noeud];
}
