#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;
return;
}
void Add(int noeud, int pere) {
if (Letter[pere] != '$')
LastLetter[noeud][0] = pere;
else
LastLetter[noeud][0] = LastLetter[pere][0];
for (int i = 1; i < LOG; i ++)
{
LastLetter[noeud][i] = LastLetter[LastLetter[noeud][i - 1]][i - 1];
}
return;
}
void TypeLetter(char L) {
Letter[++ nbOperations] = L;
SzString[nbOperations] = SzString[nbOperations - 1] + 1;
Add(nbOperations, nbOperations - 1);
return;
}
void UndoCommands(int nb) {
nb ++;
Letter[++ nbOperations] = '$';
SzString[nbOperations] = SzString[nbOperations - nb];
Add(nbOperations, nbOperations - nb);
return;
}
char GetLetter(int nb) {
int k = SzString[nbOperations] - nb;
if (Letter[nbOperations] != '$')
{
if (-- k == 0)
return Letter[nbOperations];
}
int cur = nbOperations;
for (int i = LOG - 1; i >= 0; i --)
{
if (k & (1 << i))
cur = LastLetter[cur][i];
}
return Letter[cur];
}
