#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
typedef long long llong;
const int MAXLOG = 20;
const int MAXN = 1000000 + 10;
int d[MAXN];
char value[MAXN];
struct Sparse
{
int sparse[MAXLOG][MAXN];
void pushNode(int node, int p)
{
d[node] = d[p] + 1;
sparse[0][node] = p;
for (int log = 1 ; log < MAXLOG ; ++log)
{
sparse[log][node] = sparse[log - 1][sparse[log - 1][node]];
}
}
int findKth(int node, int k)
{
for (int i = MAXLOG - 1 ; i >= 0 ; --i)
{
if (k & (1 << i))
{
node = sparse[i][node];
}
}
return node;
}
};
int cnt;
Sparse sparse;
std::vector <int> atMoment;
void Init()
{
atMoment.push_back(0);
}
void TypeLetter(char L)
{
cnt++;
value[cnt] = L;
sparse.pushNode(cnt, atMoment.back());
atMoment.push_back(cnt);
}
void UndoCommands(int U)
{
atMoment.push_back(atMoment[atMoment.size() - 1 - U]);
}
char GetLetter(int P)
{
return value[sparse.findKth(atMoment.back(), d[atMoment.back()] - P - 1)];
}
