#include "bits/stdc++.h"
using namespace std;
struct Try{
Try* parent = NULL;
Try *children[26] = {NULL};
char chr;
Try(char c, Try* p){
parent = p;
chr = c;
}
Try* add(char c){
if(children[c-'a'] != NULL) return children[c-'a'];
children[c-'a'] = new Try(c, this);
return children[c-'a'];
}
string get(){
if(parent == NULL) return ""+chr;
return parent->get() + 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()[P];
}
