#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define N (ll)1e6
ll n = 0, t = 0;
ll dpt[N], par[N][20];
ll len[N], pos[N];
string s[N][20];
char c[N];
string psum(ll a){
string r;
ll p = dpt[a];
for(ll i=0; i<20; ++i)
if(p & (1 << i)){
r = s[a][i] + r;
a = par[a][i];
}
return r;
}
ll anc(ll a, ll p){
for(ll i=0; i<20; ++i)
if(p & (1 <<i))
a = par[a][i];
return a;
}
void Init(){
}
void TypeLetter(char L) {
ll curr = pos[t];
n++;
t++;
pos[t] = n;
//aggiungo un nuovo nodo
c[n] = L;
dpt[n] = dpt[curr] + 1;
par[n][0] = curr;
for(ll i=1; i<20; ++i)
par[n][i] = par[par[n][i-1]][i-1];
s[n][0] = L;
for(ll i=1; i<20; ++i)
s[n][i] = s[par[n][i-1]][i-1] + s[n][i-1];
//cout << psum(pos[t]) << endl;
}
void UndoCommands(int U) {
t++;
pos[t] = pos[t-U-1];
//cout << psum(pos[t]) << endl;
}
char GetLetter(int P){
ll curr = pos[t];
//cout << psum(pos[t]) << endl << "get: ";;
return c[anc(curr, dpt[curr]-P-1)];
}
