#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e6 + 5 ;
const int maxl = 23 ;
int n, tempo, t[maxn], h[maxn], tab[maxl][maxn] ;
char s[maxn] ;
void TypeLetter(char L) {
n++ ; tempo++ ;
t[tempo] = n ;
s[n] = L ;
tab[0][n] = t[tempo-1] ;
h[n] = h[t[tempo-1]] + 1 ;
for(int i = 1 ; i < maxl ; i++) tab[i][n] = tab[i-1][tab[i-1][n]] ;
}
void UndoCommands(int U) {
tempo++ ;
t[tempo] = t[tempo - U - 1] ;
}
char GetLetter(int P) {
int at = t[tempo] ;
int alt = h[t[tempo]] - P - 1 ;
for(int i = maxl - 1 ; i >= 0 ; i--){
if(alt >= (1<<i)) alt -= (1<<i), at = tab[i][at] ;
}
return s[at] ;
}
void Init(){
}
