#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e6+3;
const int LOGN=22;
int cont[MAXN];
char letra[MAXN];
int dp[LOGN+2][MAXN];
int contv=0;
void update(int cur) {
int aux=dp[0][cur];
for(int i=1; i<=LOGN; i++) {
dp[i][cur]=dp[i-1][aux];
aux=dp[i][cur];
}
}
void Init() {}
void TypeLetter(char cur) {
contv++; int pai=contv-1;
if(pai==0) pai=contv;
letra[contv]=cur;
cont[contv]=cont[pai]+1;
dp[0][contv]=pai;
update(contv);
}
void UndoCommands(int val) {
contv++; int pai=contv-1-val;
if(pai==0) pai=contv;
cont[contv]=cont[pai];
dp[0][contv]=pai;
update(contv);
}
char GetLetter(int ind) {
int cur=contv;
int aux=cur;
for(int i=LOGN; i>=0; i--) {
if(cont[dp[i][aux]]>ind) {
aux=dp[i][aux];
}
}
return letra[aux];
}
