#include <iostream>
using namespace std;
const int N=5001;
const int MAX_T=2*N;
const int LG=21;
int par[MAX_T][LG];
int par_cnt[MAX_T][LG];
int ln[MAX_T];
char op[MAX_T];
int cur_t=1;
void Init()
{
op[0]='1';
}
void TypeLetter(char L)
{
// cout<<"insert "<<L<<" tm "<<cur_t<<endl;
op[cur_t]=L;
par[cur_t][0]=cur_t-1;
par_cnt[cur_t][0]=(op[cur_t-1]!='$');
ln[cur_t]=ln[cur_t-1]+1;
for(int j=1;j<LG;j++)
{
par[cur_t][j]=par[par[cur_t][j-1]][j-1];
par_cnt[cur_t][j]=par_cnt[par[cur_t][j-1]][j-1]+par_cnt[cur_t][j-1];
}
cur_t++;
}
void UndoCommands(int U)
{
// cout<<"Undo "<<U<<" tm "<<cur_t<<endl;
op[cur_t]='$';
ln[cur_t]=ln[cur_t-U-1];
par[cur_t][0]=cur_t-1-U;
par_cnt[cur_t][0]=(op[cur_t-1-U]!='$');
for(int j=1;j<LG;j++)
{
par[cur_t][j]=par[par[cur_t][j-1]][j-1];
par_cnt[cur_t][j]=par_cnt[par[cur_t][j-1]][j-1]+par_cnt[cur_t][j-1];
}
cur_t++;
}
char GetLetter(int P)
{
int cp=cur_t-1;
int len=ln[cp];
int wnt=len-P;
// cout<<"Done\n";
// cout<<len<<' '<<P<<' '<<wnt<<endl;
char c='1';
if(op[cp]!='$')
{
wnt--;
c=op[cp];
}
// cout<<"Gojo "<<wnt<<endl;
for(int j=LG-1;j>=0;j--)
{
// cout<<"Minus "<<cp<<' '<<j<<' '<<par_cnt[cp][j]<<endl;
if(wnt>=(par_cnt[cp][j]))
{
wnt-=par_cnt[cp][j];
cp=par[cp][j];
c=op[cp];
}
// if(op[cp]!='$')
// {
// wnt--;
// c=op[cp];
// }
}
// cout<<"HE ";
// cout<<cp<<endl;
// cout<<wnt<<endl;
return c;
}
