#include <bits/stdc++.h>
using namespace std;
using pic = pair<int, char>;
const int N = 1<<20;
const int LN = 20;
int cnt;
char chr[N];
int len[N];
int par[N][LN];
int ptr[N];
inline int link(int p, char c)
{
chr[++cnt] = c;
par[cnt][0] = p;
len[cnt] = len[p]+1;
for (int i = 1; (1<<i) <= len[cnt]; ++i)
par[cnt][i] = par[par[cnt][i-1]][i-1];
return cnt;
}
void Init() {
//printf("Init()\n");
}
int vc;
void TypeLetter(char L) {
//printf("TypeLetter(%c)\n", L);
++vc;
ptr[vc] = link(ptr[vc-1], L);
}
void UndoCommands(int U)
{
//printf("UndoCommands(%d)\n", U);
U = min(U, vc);
++vc;
ptr[vc] = ptr[vc-U-1];
}
char GetLetter(int P)
{
int u = ptr[vc];
P = len[ptr[vc]]-P-1;
for (int i = LN-1; i >= 0; --i)
if ((1<<i)&P) u = par[u][i];
//printf("GetLetter(%d) = %c\n", P, ans);
return chr[u];
}
