#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
#define pb push_back
#define f first
#define s second
const int MAXN = 1e6 + 1e3;
const int LOGN = 21;
char lets[MAXN];
int L[MAXN], nLetI[MAXN], jmp[MAXN][LOGN];
void Init() {
memset(lets, 0, sizeof(lets));
memset(L, 0, sizeof(L));
memset(nLetI, 0, sizeof(nLetI));
memset(jmp, 0, sizeof(jmp));
}
int cI = 1;
inline void computeJump(int i) {
for (int log = 1; log < LOGN; log++) {
jmp[i][log] = jmp[jmp[i][log - 1]][log - 1];
}
}
void TypeLetter(char cLet) {
lets[cI] = cLet;
L[cI] = L[cI - 1] + 1;
if (lets[cI - 1] == 0) {
nLetI[cI] = nLetI[cI - 1];
} else {
nLetI[cI] = cI - 1;
}
jmp[cI][0] = nLetI[cI];
computeJump(cI);
cI++;
}
void UndoCommands(int U) {
L[cI] = L[cI - U - 1];
if (lets[cI - U - 1] == 0) {
nLetI[cI] = nLetI[cI - U - 1];
} else {
nLetI[cI] = cI - U - 1;
}
jmp[cI][0] = nLetI[cI];
computeJump(cI);
cI++;
}
char GetLetter(int P) {
int nJ = L[cI - 1] - P - 1;
int i = cI - 1;
if (lets[i] == 0) {
i = nLetI[i];
}
for (int log = LOGN - 1, jmps = 1 << log; log >= 0; log--, jmps /= 2) {
if (jmps <= nJ) {
i = jmp[i][log];
nJ -= jmps;
}
}
return lets[i];
}
