#include <iostream>
using namespace std;
struct StringTree
{
char c='1';
int s,e;
int len=0;
StringTree* next[2];
StringTree(int l,int r,bool p=0)
{
s=l;
e=r;
if(s!=e and !p)
{
int mid=(s+e)/2;
next[0]=new StringTree(s,mid);
next[1]=new StringTree(mid+1,e);
}
}
char get(int&x)
{
if(s==e)
return c;
int mid=(s+e)/2;
return next[(x>mid)]->get(x);
}
};
const int MAXT=2e6+1;
StringTree* st[MAXT];
int tm=1;
StringTree* Update(StringTree* prev,char&c,int&ind)
{
StringTree* tp=new StringTree(prev->s,prev->e,1);
tp->len=prev->len+1;
tp->c=c;
if(prev->s==prev->e)
return tp;
int mid=(prev->s+prev->e)/2;
if(ind<=mid)
{
tp->next[1]=prev->next[1];
tp->next[0]=Update(prev->next[0],c,ind);
}
else
{
tp->next[0]=prev->next[0];
tp->next[1]=Update(prev->next[1],c,ind);
}
return tp;
}
void Init()
{
st[0]=new StringTree(0,MAXT);
}
void TypeLetter(char L)
{
st[tm]=Update(st[tm-1],L,st[tm-1]->len);
tm++;
}
void UndoCommands(int U)
{
st[tm]=st[tm-U-1];
tm++;
}
char GetLetter(int P)
{
return st[tm-1]->get(P);
}
