#include "bits/stdc++.h"
using namespace std;
const int LOG2 = 20;
struct Try{
Try* parent = NULL;
Try *children[26] = {NULL};
int h;
char chr;
Try *jump[LOG2] = {NULL};
Try(char c, Try* p){
parent = p;
chr = c;
if(p==NULL) h = 0;
else h = parent->h+1;
Try *now = this;
for(int i = 0; i < LOG2; i++){
if(i == 0) now = parent;
else if(now == NULL) now = NULL;
else now = now->jump[i-1];
jump[i] = now;
}
}
Try* add(char c){
if(children[c-'a'] != NULL) return children[c-'a'];
children[c-'a'] = new Try(c, this);
return children[c-'a'];
}
char get(int j){
Try *now = this;
for(int i = LOG2; i >= 0; i--){
// cout << j << '\n';
if(1<<i > j) continue;
j -= 1<<i;
now = now->jump[i];
}
return now->chr;
}
};
int i=1;
Try *tries[1000005];
void Init(){
tries[0] = NULL;
};
void TypeLetter(char L){
tries[i]=new Try(L, tries[i-1]);
i++;
}
void UndoCommands(int U){
tries[i]=tries[i-U-1];
i++;
}
char GetLetter(int P){
return tries[i-1]->get(tries[i-1]->h-P);
}
