#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vt vector
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#pragma GCC optimize ("O3")
#pragma GCC optimize ("O2")
#define F first
#define S second
//#define endl '\n'
//#define int long long
#define inbuf_len 1 << 16
#define outbuf_len 1 << 16
using namespace std;
const int const_lg = 20;
struct node
{
char val;
int h;
vt<int> children, parent;
node() { h = 0; }
node(char val_, int parent_, int h_)
{
val = val_, h = h_;
parent.resize(const_lg + 1);
parent[0] = parent_;
}
};
vt<node> trie;
vt<int> commands;
void Init()
{
trie.pb({'A', 0, -1});
commands.pb(0);
}
void TypeLetter(char L)
{
int i = *commands.rbegin();
trie[i].children.pb(sz(trie));
trie.pb({L, i, trie[i].h + 1});
for(int i = 1, v = sz(trie) - 1; i <= const_lg; i++)
trie[v].parent[i] = trie[trie[v].parent[i - 1]].parent[i - 1];
commands.pb(sz(trie) - 1);
}
void UndoCommands(int U)
{
int n = sz(commands);
commands.pb(commands[n - U - 1]);
}
char GetLetter(int P)
{
int v = *commands.rbegin();
for(int k = const_lg; k >= 0; k--)
if (trie[trie[v].parent[k]].h >= P ) v = trie[v].parent[k];
return trie[v].val;
}
