#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int N = 1e6 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
int ptr[N][26];
int anc[N][20];
int pos[N];
int d[N];
int cur,cnt,node;
char a[N];
//#include "grader.cpp"
void Init() {}
void TypeLetter(char L) {
int v = L - 'a';
if (!ptr[cur][v]) {
ptr[cur][v] = ++node;
a[node] = L;
anc[node][0] = cur;
for (int i = 1; i < 20; i++)
anc[node][i] = anc[anc[node][i - 1]][i - 1];
d[node] = d[cur] + 1;
}
cur = ptr[cur][v];
pos[++cnt] = cur;
}
void UndoCommands(int U) {
pos[cnt + 1] = pos[cnt - U];
cnt++;
cur = pos[cnt];
}
char GetLetter(int P) {
int dis = d[cur] - (P + 1);
int v = cur;
for (int i = 0; i < 20; i++, dis >>= 1)
if (dis & 1)
v = anc[v][i];
return a[v];
}
