#include <vector>
#include <array>
#include <string>
using namespace std;
struct Trie
{
array<int, 26> empty;
vector<array<int, 26>> child;
vector<array<int, 21>> up;
vector<int> len;
string chars;
Trie()
{
empty.fill(-1);
child.push_back(empty);
up.push_back(array<int, 21>());
up[0].fill(0);
len.push_back(0);
chars.push_back(' ');
}
int add(int v, char c)
{
if (child[v][c - 'a'] == -1)
{
child[v][c - 'a'] = child.size();
child.push_back(empty);
up.push_back(array<int, 21>());
up[child[v][c - 'a']][0] = v;
for (int i = 1; i < 21; ++i) up[child[v][c - 'a']][i] = up[up[child[v][c - 'a']][i - 1]][i - 1];
len.push_back(len[v] + 1);
chars.push_back(c);
}
v = child[v][c - 'a'];
return v;
}
char get(int v, int i)
{
i = len[v] - i - 1;
for (int j = 20; j >= 0; --j) if (i & (1 << j)) v = up[v][j];
return chars[v];
}
};
Trie trie;
vector<int> pos{0};
void Init()
{
}
void TypeLetter(char L)
{
pos.push_back(trie.add(pos.back(), L));
}
void UndoCommands(int U)
{
//2
pos.push_back(pos[(int)pos.size() - U - 1]);
}
char GetLetter(int P)
{
return trie.get(pos.back(), P);
}
