#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
using namespace std;
const int N = 1e6 + 5, B = 20;
int ancetres[N][B];
int prof[N];
char lettre[N];
int noeudInst[N];
int nNoeuds = 0, noeudCur = 0;
void dbg(){
/*vector<int> parcours;
int noeud = noeudCur;
while (noeud > 0){
parcours.pb(noeud);
noeud = ancetres[noeud][0];
}
reverse(parcours.begin(), parcours.end());
cout << "DBG\n";
for (int e : parcours)
cout << lettre[e];
cout << endl;
for (int e : parcours)
cout << prof[e] << " ";
cout << endl << endl;*/
}
void Init() {
prof[0] = 0;
noeudInst[0] = 0;
nNoeuds = 1;
for (int noeud = 0; noeud < N; ++noeud)
for (int ind = 0; ind < B; ++ind)
ancetres[noeud][ind] = -1;
}
void TypeLetter(char L) {
int pere = noeudCur;
noeudInst[nNoeuds] = nNoeuds;
noeudCur = nNoeuds++;
prof[noeudCur] = prof[pere] + 1;
lettre[noeudCur] = L;
int mid = pere, ind;
for (ind = 0; ind < B && ancetres[mid][ind] != -1; ++ind){
ancetres[noeudCur][ind] = mid;
mid = ancetres[mid][ind];
}
ancetres[noeudCur][ind] = mid;
// dbg();
}
void UndoCommands(int U) {
noeudCur = noeudInst[nNoeuds - 1 - U];
noeudInst[nNoeuds++] = noeudCur;
//dbg();
}
char GetLetter(int P) {
int noeud = noeudCur;
for (int i = B - 1; i >= 0; --i){
if (ancetres[noeud][i] != -1 && prof[ancetres[noeud][i]] > P)
noeud = ancetres[noeud][i];
}
return lettre[noeud];
}
