#include<stdio.h>
const int MAXC = 1000005;
const int lgMAXC = 20;
struct node{
char letter;
int level;
node* parent[lgMAXC];
node(char letter, node* par): letter(letter){
parent[0] = par;
if(par != NULL) level = par->level + 1; else level = 0;
for(int i=1; i<lgMAXC; i++){
if(parent[i-1] == NULL) parent[i] = NULL;
else parent[i] = parent[i-1]->parent[i-1];
}
}
};
node* Commands[MAXC];
node* now;
int N;
void Init(){
now = new node(0, NULL);
Commands[1] = now; N = 1;
}
void TypeLetter(char L){
Commands[++N] = new node(L, now);
now = Commands[N];
}
void UndoCommands(int U){
int val = N - U; Commands[++N] = Commands[val];
now = Commands[N];
}
char GetLetter(int P){ ++P;
node* tmp = now; int L = now->level - P;
for(int i=0; (1<<i)<=L; i++) if(L & (1<<i)){
tmp = tmp->parent[i];
}
return tmp->letter;
}
