#include <bits/stdc++.h>
using namespace std;
int const MAX=1e6+5;
int const LOG=22;
vector<int>stare;
int h[MAX];
int lift[MAX][LOG];
int id;
char carac[MAX];
void Init(){
stare.push_back(0);
h[0]=-1;
}
void TypeLetter(char L){
int tata=stare.back();
++id;
stare.push_back(id);
carac[id]=L;
h[id]=h[tata]+1;
lift[id][0]=tata;
int i;
for(i=1;i<LOG;++i)
lift[id][i]=lift[lift[id][i-1]][i-1];
}
void UndoCommands(int U){
stare.push_back(stare[stare.size()-U-1]);
}
char GetLetter(int P){
int nod=stare.back();
int dif=h[nod]-P;
int i;
for(i=0;i<LOG;++i)
if(dif&(1<<i))
nod=lift[nod][i];
return carac[nod];
}
