#include<bits/stdc++.h>
using namespace std;
int cnt=0;
const int maxn=1e6+10;
const int maxk=21;
int dp[maxn][maxk], prof[maxn], last;
int val[maxn];
char resp[maxn];
void Init(){
}
void TypeLetter(char L){
cnt++;
prof[cnt]=prof[last]+1;
dp[cnt][0]=last;
for(int k=1;k<maxk;k++) dp[cnt][k]=dp[dp[cnt][k-1]][k-1];
val[cnt]=cnt; resp[cnt]=L;
// printf("! %c\n", resp[cnt]);
last=cnt;
}
void UndoCommands(int U){
cnt++;
last=val[cnt]=val[cnt-U-1];
}
char GetLetter(int P){
int at=val[cnt];
// while(at){
// cout << resp[at];
// at=dp[at][0];
// }
// cout << '\n';
at=val[cnt];
P=prof[at]-(P+1);
for(int k=0;k<maxk;k++) if(P&(1<<k)) at=dp[at][k];
return resp[at];
}
