#include<bits/stdc++.h>
//#include "scrivener.pas"
//#include "scrivener.h"
using namespace std;
const int maxn=1000000+10,lg=20;
int par[maxn],sp[lg][maxn],vas[maxn],ted[maxn];
int now=-1;
char wtf[maxn];
void Init(){
}
void calsp(int i){
sp[0][i]=par[i];
for(int j=1;j<lg;j++){
sp[j][i]=sp[j-1][sp[j-1][i]];
}
}
void TypeLetter(char L){
now++;
vas[now]=1;
wtf[now]=L;
if(now==0){
ted[now]=1;
return ;
}
if(vas[now-1]==1){
par[now]=now-1;
ted[now]=ted[par[now]]+1;
calsp(now);
return ;
}
par[now]=par[now-1];
ted[now]=ted[par[now]]+1;
calsp(now);
}
void UndoCommands(int U){
now++;
vas[now]=0;
par[now]=now-U-1;
if(vas[par[now]]==0){
par[now]=par[par[now]];
}
ted[now]=ted[par[now]];
}
char GetLetter(int P){
P++;
int te=ted[now];
int fn=now;
if(vas[now]==0){
fn=par[now];
}
int x=te-P;
for(int i=0;i<lg;i++){
if((x>>i)&1){
fn=sp[i][fn];
}
}
return wtf[fn];
}
