#include <iostream>
#include <cstdio>
using namespace std;
// <|°_°|>
const int MAX_OPERATIONS = (1000 * 1000 + 1);
const int LOG = (20);
char Letter[MAX_OPERATIONS];
int SzString[MAX_OPERATIONS];
int LastLetter[MAX_OPERATIONS][LOG];
int nbOperations = 0;
void Init() {
Letter[0] = '$';
SzString[0] = 0;
LastLetter[0][0] = -1;
return;
}
void Add(int noeud) {
if (Letter[noeud - 1] != '$')
LastLetter[noeud][0] = noeud - 1;
else
LastLetter[noeud][0] = LastLetter[noeud - 1][0];
for (int i = 1; i < LOG; i ++)
{
LastLetter[noeud][i] = LastLetter[LastLetter[noeud][i - 1]][i - 1];
if (LastLetter[noeud][i] < 0)
return;
}
return;
}
void TypeLetter(char L) {
Letter[++ nbOperations] = L;
SzString[nbOperations] = SzString[nbOperations - 1] + 1;
Add(nbOperations);
return;
}
void UndoCommands(int nb) {
nb ++;
Letter[++ nbOperations] = '$';
SzString[nbOperations] = SzString[nbOperations - nb];
if (Letter[nbOperations - nb] != '$')
LastLetter[nbOperations][0] = nbOperations - nb;
else
LastLetter[nbOperations][0] = LastLetter[nbOperations - nb][0];
return;
}
char GetLetter(int nb) {
int k = SzString[nbOperations] - nb;
int cur = nbOperations;
if (Letter[nbOperations] == '$')
cur = LastLetter[nbOperations][0];
if (-- k == 0)
return Letter[cur];
for (int i = 0; i < LOG; i ++)
{
if (LastLetter[cur][i] < 0)
return Letter[cur];
if (k & (1 << i))
cur = LastLetter[cur][i];
}
return Letter[cur];
}
