#include <bits/stdc++.h>
// mrrrow meeow :3
// go play vivid/stasis now! https://vividstasis.gay
#define fo(i, a, b) for (auto i = (a); i < (b); i++)
#define of(i, a, b) for (auto i = (b); i-- > (a);)
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound
#define be(a) a.begin(), a.end()
using namespace std;
int ____init = [] {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
return 0;
}();
struct Node {
char c;
array<int, 26> children;
array<int, 20> parents;
int d = -1;
};
vector<Node> nodes = {Node()};
int curr = 0;
vector<int> been = {0};
void Init() {}
void TypeLetter(char c) {
c -= 'a';
if (nodes[curr].children[c] != 0) {
curr = nodes[curr].children[c];
been.pb(curr);
return;
}
nodes[curr].children[c] = nodes.size();
nodes.pb(Node());
nodes.back().c = c + 'a';
nodes.back().d = nodes[curr].d + 1;
nodes.back().parents[0] = curr;
fo(i, 1, 20) nodes.back().parents[i] = nodes[nodes.back().parents[i - 1]].parents[i - 1];
curr = nodes[curr].children[c];
been.pb(curr);
}
void UndoCommands(int u) {
curr = been[been.size() - u - 1];
been.pb(curr);
}
char GetLetter(int i) {
i = nodes[curr].d - i;
int j = curr;
fo(k, 0, 20) {
if (i & 1) j = nodes[j].parents[k];
i >>= 1;
}
return nodes[j].c;
}
