#include <cstdio>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll=long long;
#define ALL(x) x.begin(), x.end()
int p[20][1<<20], a[1<<20], ptr, dep[1<<20];
vector<int> chain;
void Init()
{
}
void TypeLetter(char l)
{
a[1+ptr] = l; p[0][1+ptr] = ptr; dep[1+ptr] = dep[ptr]+1;
for (int j = 1; j < 20; ++j) p[j][1+ptr] = p[j-1][p[j-1][1+ptr]];
chain.push_back(++ptr); a[ptr] = l;
}
void UndoCommands(int u)
{
ptr=chain[max((int)chain.size()-u-1, 0)]; chain.push_back(ptr);
}
char GetLetter(int k)
{
int c = ptr; k = dep[c] - k-1;
for (int j = 20; j--;) if (k & (1 << j)) c = p[j][c];
return a[c];
}
