#include<vector>
using namespace std;
struct PST
{
vector<char> tree;
vector<int> left, right, root;
int height, t, base;
PST(int a, int b, int rn)
{
base=height=1, t=0;
while(base<a) height++, base=base<<1;
int tmp=base*2+2+height*b+5;
tree.resize(tmp);
left.resize(tmp);
right.resize(tmp);
root.resize(rn+2);
root[0]=setup(1,base);
}
int setup(int ns, int nf)
{
int k=t++;
tree[k]=0;
if(ns<nf)
{
int mid=(ns+nf)>>1;
left[k]=setup(ns,mid);
right[k]=setup(mid+1,nf);
}
return k;
}
void update_Kth_tree(int bef, int k, int idx, char val)
{
root[k]=make(root[bef],idx,val);
}
int make(int bef, int idx, char val, int ns=1, int nf=-1)
{
if(nf==-1) nf=base;
if(idx<ns || nf<idx) return bef;
int k=t++;
if(ns==nf) tree[k]=val;
else
{
int mid=(ns+nf)>>1;
left[k]=make(left[bef],idx,val,ns,mid);
right[k]=make(right[bef],idx,val,mid+1,nf);
tree[k]=val;
}
return k;
}
char get_char(int num, int idx, int ns=1, int nf=-1)
{
if(nf==-1) nf=base;
if(ns==nf) return tree[num];
int mid=(ns+nf)>>1;
if(ns<=idx && idx<=mid)
return get_char(left[num],idx,ns,mid);
if(mid+1<=idx && idx<=nf)
return get_char(right[num],idx,mid+1,nf);
}
};
int len[1000002], cnt;
PST T(1000002,1000002,1000002);
void Init() {}
void TypeLetter(char L)
{
cnt++;
len[cnt]=len[cnt-1]+1;
T.update_Kth_tree(cnt-1,cnt,len[cnt],L);
}
void UndoCommands(int U)
{
cnt++;
len[cnt]=len[cnt-U-1];
T.update_Kth_tree(cnt-U-1,cnt,len[cnt]+1,0);
}
char GetLetter(int P)
{
return T.get_char(T.root[cnt],P+1);
}
