#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int sz[MAXN];
char op[MAXN];
pair<int, int> dp[20][MAXN];
int cnt;
void Init(){
sz[0] = 0;
cnt = 0;
}
void TypeLetter(char l){
cnt ++;
sz[cnt] = sz[cnt - 1] + 1;
op[cnt] = l;
dp[0][cnt] = {cnt, sz[cnt]};
for(int k=1; k<20; k++) dp[k][cnt] = {cnt, sz[cnt]};
}
void UndoCommands(int u){
cnt ++;
sz[cnt] = sz[cnt - 1];
dp[0][cnt] = {cnt - u - 1, sz[cnt - u - 1]};
for(int k=1; k<20; k++){
dp[k][cnt].first = dp[k - 1][dp[k - 1][cnt].first].first;
dp[k][cnt].second = dp[k - 1][cnt].second + dp[k - 1][dp[k - 1][cnt].first].second;
}
}
char GetLetter(int p){
int cur = cnt;
for(int k=19; k>=0; k--){
if(sz[cnt] - dp[k][cur].second < p){
p -= dp[k][cur].second;
cur = dp[k][cur].first;
}
}
return op[dp[0][cur].first];
}
