#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e6 + 69;
const int LG = 20;
int N = 0;
char ar[MAX];
int len[MAX], par[MAX][LG];
void Init()
{
ar[0] = '$';
}
void TypeLetter(char L)
{
++N;
ar[N] = L; len[N] = len[N-1] + 1; par[N][0] = N-1;
for (int i = 1; i < LG; ++i)
par[N][i] = par[par[N][i-1]][i-1];
}
void UndoCommands(int U)
{
++N;
par[N][0] = par[N-U-1][0]; len[N] = len[N-U-1]; ar[N] = ar[N-U-1];
for (int i = 1; i < LG; ++i)
par[N][i] = par[par[N][i-1]][i-1];
}
char GetLetter(int P)
{
P = len[N] - P - 1;
int cur = N;
for (int i = 0; i < LG; ++i)
if (P >> i & 1)
cur = par[cur][i];
return ar[cur];
}
