#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1000009;
struct Cvor{
int L,R,val;
Cvor(){L=0;R=0;val=0;}
Cvor(int L,int R,int val){this->L=L;this->R=R;this->val=val;}
};
int i;
Cvor seg[20000000];
int indx=0;
int root[N];
void upd(int old,int node,int l,int d,int ind,int val){
int s=l+d>>1;
if(l==d&&d==ind){
seg[node]=Cvor(0,0,val);
return;
}
if(ind<=s){
seg[node].L=++indx;
seg[node].R=seg[old].R;
upd(seg[old].L,indx,l,s,ind,val);
}
else{
seg[node].R=++indx;
seg[node].L=seg[old].L;
upd(seg[old].R,indx,s+1,d,ind,val);
}
}
int siz(int node,int l,int d){
if(l==d) return l;
int s=l+d>>1;
if(seg[node].R) return siz(seg[node].R,s+1,d);
return siz(seg[node].L,l,s);
}
int query(int node,int l,int d,int ind){
if(l==d) return seg[node].val;
int s=l+d>>1;
if(ind<=s) return query(seg[node].L,l,s,ind);
return query(seg[node].R,s+1,d,ind);
}
void Init(){
i=0;
return;
}
void TypeLetter(char L){
i++;
root[i]=++indx;
upd(root[i-1],root[i],0,N,siz(root[i-1],0,N)+1,L-'a');
return;
}
void UndoCommands(int U){
i++;
root[i]=root[i-U-1];
return;
}
char GetLetter(int P){
return char('a'+query(root[i],0,N,P+1));
}
