#include <iostream>
using namespace std;
char last;
int vis[1000005][2],loc,l[30000005],r[30000005],cnt,v;
char val,tree[30000005];
void Init(){
vis[0][0]=0;
vis[0][1]=0;
}
void clone(int a,int b)
{
l[b]=l[a];
r[b]=r[a];
tree[b]=tree[a];
return ;
}
int change(int node,int s,int e)
{
//cout<<s<<" "<<e<<endl;
cnt++;
clone(node,cnt);
if(s==e)
{
tree[cnt]=val;
return cnt;
}
long long int now=cnt;
if(vis[v][1]<=(s+e)/2)
{
l[now]=change(l[now],s,(s+e)/2);
}
else r[now]=change(r[now],(s+e)/2+1,e);
return now;
}
char find(int node,int s,int e){
if(s==e)return tree[node];
if(loc<=(s+e)/2)return find(l[node],s,(s+e)/2);
else return find(r[node],(s+e)/2+1,e);
}
void TypeLetter(char L) {
v++;
val=L;
vis[v][0]=cnt+1;
vis[v][1]=vis[v-1][1]+1;
change(vis[v-1][0],1,1000000);
}
void UndoCommands(int U) {
v++;
vis[v][0]=vis[v-U-1][0];
vis[v][1]=vis[v-U-1][1];
return ;
}
char GetLetter(int P) {
loc=P+1;
return find(vis[v][0],1,1000000);
}
