#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
const int mxn = 1e6 + 10;
int nxt[mxn][21], sz[mxn], cnt = 0;
char c[mxn];
void Init() { }
void TypeLetter(char L) {
cnt++;
c[cnt] = L;
sz[cnt] = sz[cnt - 1] + 1;
nxt[cnt][0] = cnt - 1;
for (int i = 1; i <= 20; i++) nxt[cnt][i] = nxt[nxt[cnt][i - 1]][i - 1];
}
void UndoCommands(int U) {
cnt++;
sz[cnt] = sz[cnt - U - 1];
nxt[cnt][0] = nxt[cnt - U - 1][0];
c[cnt] = c[cnt - U - 1];
for (int i = 1; i <= 20; i++) nxt[cnt][i] = nxt[nxt[cnt][i - 1]][i - 1];
}
char GetLetter(int P) {
int len = sz[cnt] - P - 1;
int ans = cnt;
for (int i = 20; i >= 0; i--) {
if (len & (1 << i)) ans = nxt[ans][i];
}
return c[ans];
}
