#include <bits/stdc++.h>
// author: aykhn
using namespace std;
#define mpr make_pair
#define pb push_back
#define fi first
#define se second
const int MXN = 1e6 + 5;
const int LOG = 21;
int n;
int adj[MXN][26];
int p[LOG][MXN];
char val[MXN];
int dep[MXN];
vector<int> s;
void Init()
{
s.clear();
for (int i = 0; i <= n; i++)
{
for (int j = 0; j < LOG; j++) p[j][i] = 0;
for (int j = 0; j < 26; j++) adj[i][j] = 0;
val[i] = '$';
}
s.pb(0);
n = 0;
}
void TypeLetter(char L)
{
int cur = s.back();
if (adj[cur][L - 'a']) s.pb(adj[cur][L - 'a']);
else
{
adj[cur][L - 'a'] = ++n;
p[0][n] = cur;
for (int i = 1; i < LOG; i++) p[i][n] = p[i - 1][p[i - 1][n]];
dep[n] = dep[cur] + 1;
val[n] = L;
s.pb(n);
}
}
void UndoCommands(int U)
{
s.pb(s[(int)s.size() - U - 1]);
}
char GetLetter(int P)
{
int cur = s.back();
int d = dep[cur] - P - 1;
for (int i = LOG - 1; i >= 0; i--)
{
if (d >> i & 1) cur = p[i][cur];
}
return val[cur];
}
