#include <bits/stdc++.h>
using namespace std;
void Init(){
return ;
}
int sz[1000001],chr[1000001];
int P[1000001][20];
int ind = 1;
void TypeLetter(char c){
sz[ind] = sz[ind-1]+1;
chr[ind] = (c-'a');
P[ind][0] = ind-1;
for(int i = 1;i<20;i++){
P[ind][i] = P[P[ind][i-1]][i-1];
}
ind++;
}
void UndoCommands(int u){
int lol = ind-(u+1);
sz[ind] = sz[lol];
chr[ind] = chr[lol];
for(int i = 0;i<20;i++){
P[ind][i] = P[lol][i];
}
ind++;
}
char GetLetter(int p){
int xd = sz[ind-1]-(p+1);
int cur = ind-1;
for(int i = 19;i>=0;i--){
if(xd>=(1<<i)){
cur = P[cur][i];
xd-=(1<<i);
}
}
return char(chr[cur]+'a');
}/*
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
init();
TypeLetter('a');
TypeLetter('b');
cout<<GetLetter(1);
return 0;
}
*/
