#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5, logn = 20;
struct cmd
{
bool undo;
int x, sum;
char c;
};
int n = 0;
int jump[maxn][logn];
cmd v[maxn];
void NewCommand() // spracuj ten nakonci v ak vies ze musis ist x znakov dozadu
{
int x = v[n-1].x + 1;
int pv = n - 1 - x;
if (pv == -1) return;
v[n-1].sum += v[pv].sum;
if (v[pv].undo) pv = jump[pv][0];
jump[n-1][0] = pv;
for (int i = 1; i < logn; i++)
jump[n-1][i] = jump[jump[n-1][i-1]][i-1];
}
void Init() { }
void TypeLetter(char L)
{
v[n++] = {false, 0, 1, L};
NewCommand();
}
void UndoCommands(int U)
{
v[n++] = {true, U, 0, '.'};
NewCommand();
}
char GetLetter(int P)
{
int num = v[n-1].sum, b = num - P;
int id = n-1;
if (!v[id].undo) b--;
for (int i = 0; i < logn; i++)
if ((1 << i) & b) id = jump[id][i];
return v[id].c;
}
