#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define f first
#define s second
#define dbg(v) cerr << #v << " = " << v << "\n"
#define fall(i, s, n) for(int i=s; i<n; i++)
#define rfall(i, s, n) for(int i=s; i>=n; i--)
typedef pair<int, int> pii;
typedef tuple<int, int, int> trio;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e6 + 7;
const int MAXL = 23;
int sz[MAXN];
char last[MAXN];
int sparse[MAXN][MAXL], t=0;
void build(){
fall(i, 1, MAXL) sparse[t][i] = sparse[sparse[t][i-1]][i-1];
}
void Init() {}
void TypeLetter(char L) {
last[t] = L, sz[t] = sz[t-1]+1, sparse[t][0]=t-1;
build(), t++;
}
void UndoCommands(int U) {
last[t] = last[t-U-1], sz[t]=sz[t-U-1], sparse[t][0]=t-U-1;
build(), t++;
}
char GetLetter(int P) {
int x=t-1, s=sz[t-1];
rfall(i, MAXL-1, 0)
if(sz[sparse[x][i]] >= P+1) s = sz[sparse[x][i]], x = sparse[x][i];
return last[x];
}
