#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-ind;
for(int i=0;i<lg;++i){ if(ind&(1<<i)) ret=(ret->anc[i]); assert(ret!=NULL);}
return ret->c;
}
};
vc<node*> tpoi;
node* cur;
void Init(){
cur = new node('.', NULL, 0);
tpoi.push_back(cur);
}
void TypeLetter(char L){
cur = new node(L, cur, (cur->hei) +1);
tpoi.push_back(cur);
}
void UndoCommands(int U){
cur = tpoi[tpoi.size()-1 - U];
tpoi.push_back(cur);
}
char GetLetter(int P){
return cur->getkth(P+1);
}
