#include <bits/stdc++.h>
#define vc vector
using namespace std;
const int lg=20;
struct node{
char c;
node* anc[lg];
int hei;
node(char c_, node* par, int hei_){
c=c_;hei=hei_;
if(par==NULL) anc[0]=this;
else anc[0]=par;
for(int i=1;i<lg;++i) anc[i] = (anc[i-1]->anc)[i-1];
}
char getkth(int ind){
node* ret =this;
ind=hei-1 -ind;
for(int i=0;i<lg;++i){ if(ind&(1<<i)) ret=ret->anc[i]; assert(ret!=NULL);}
return ret->c;
}
};
vc<node> tr;
vc<node*> tpoi;
node* cur;
void Init(){
tr.push_back(node('.', NULL, 0));
cur=(&tr[tr.size()-1]);
}
void TypeLetter(char L){
tr.push_back(node(L, cur, (cur->hei) +1));
cur=(&tr[tr.size()-1]);
tpoi.push_back(cur);
}
void UndoCommands(int U){
tpoi.push_back(tpoi[tpoi.size()-1 - U]);
cur=(tpoi[tpoi.size()-1]);
}
char GetLetter(int P){
return cur->getkth(P);
}
