#include <bits/stdc++.h>
using namespace std;
const int N=1e6+67;
pair<char,int> up[N][22];
int sz[N],cnt=1;
void Init() {
}
void TypeLetter(char L) {
sz[cnt]=sz[cnt-1]+1;
up[cnt][0]={L,cnt};
for(int i=1;i<22;i++){
up[cnt][i]=up[up[cnt][i-1].second-1][i-1];
}
cnt++;
}
void UndoCommands(int U) {
int take=cnt-U-1;
for(int i=0;i<22;i++)up[cnt][i]=up[take][i];
sz[cnt]=sz[take];
cnt++;
}
char GetLetter(int P) {
int take=cnt-1;
int jump=sz[take]-P-1;
// cout<<jump<<endl;
// return 'a';
for(int i=21;i>=0;i--){
if((1<<i)<=jump){
jump-=(1<<i);
take=up[take][i].second-1;
}
}
return up[take][0].first;
}
