#include <bits/stdc++.h>
using namespace std;
const int mxN = (int)1e6+2;
const int mxLg = 160;
template<int SZ>
struct PersistentSegTree{
char seg[SZ*mxLg];
int L[SZ*mxLg], R[SZ*mxLg];
int IND;
void init(){ IND = 1; L[IND]=R[IND]=0; }
int newChild(char x){
int ind = ++IND;
L[ind]=R[ind]=0; seg[ind]=x;
return ind;
}
int newParent(int l, int r){
int ind = ++IND;
L[ind] = l, R[ind] = r;
return ind;
}
int upd(int x, char v, int p, int l=1, int r=SZ){
if(!p) return 0;
if(l==r) return newChild(v);
int mid = (l+r)/2;
if(!L[p]) L[p] = ++IND;
if(!R[p]) R[p] = ++IND;
if(x<=mid) return newParent(upd(x,v,L[p],l,mid),R[p]);
return newParent(L[p],upd(x,v,R[p],mid+1,r));
}
char query(int x, int p, int l=1, int r=SZ){
if(l==r) return seg[p];
int mid = (l+r)/2;
if(x<=mid) return query(x,L[p],l,mid);
return query(x,R[p],mid+1,r);
}
};
PersistentSegTree<mxN> seg;
int rt[mxN], sz[mxN];
int cur;
void Init(){ seg.init(); rt[0] = 1; };
void TypeLetter(char L){
sz[cur+1] = sz[cur]+1;
rt[cur+1] = seg.upd(sz[cur]+1,L,rt[cur]);
cur++;
};
void UndoCommands(int U){
sz[cur+1] = sz[cur-U];
rt[cur+1] = rt[cur-U];
cur++;
};
char GetLetter(int P){ return seg.query(P+1,rt[cur]); };
