#include <string>
#include <vector>
#include <iostream>
using namespace std;
int const N=1e6+10;
struct node
{
char c=' ';
int sz=0;
node* par[22]={};
node()
{
for (int i=0;i<22;i++)
par[i]=NULL;
}
};
vector<node*>re;
node* cur;
void Init()
{
cur=NULL;
re.push_back(cur);
}
void TypeLetter(char L)
{
if (cur==NULL)
{
cur=new node();
cur->c=L;
cur->sz=1;
re.push_back(cur);
return;
}
node* z=new node();
z->par[0]=cur;
for (int i=1;i<22;i++)
{
if (z->par[i-1]==NULL)
break;
z->par[i]=z->par[i-1]->par[i-1];
}
z->c=L;
z->sz=cur->sz+1;
cur=z;
re.push_back(cur);
}
void UndoCommands(int U)
{
cur=re[re.size()-U-1];
re.push_back(cur);
}
char GetLetter(int P)
{
P=cur->sz-P-1;
node* temp=cur;
for (int i=0;i<22;i++)
{
if ((1<<i)&P)
temp=temp->par[i];
}
return temp->c;
}
