#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;
#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
struct trie{
trie* let[26];
trie* par;
char last;
int s=0;
trie(){
FOR(i,26) let[i] = nullptr;
}
trie(char x, int ns, trie* p){
FOR(i,26) let[i] = nullptr;
last = x;
s = ns;
par = p;
}
trie* add(char x){
//cout<<"adding "<<x<<" to "<<last<<endl;
if(let[x-'a']==nullptr) let[x-'a'] = new trie(x, s+1, par->let[last-'a']);
return let[x-'a'];
}
};
static vector<trie*> history;
unordered_map<trie*, vector<trie*> > anc;
trie root;
void prepr(trie* node){
anc[node].assign(25, root.let[0]);
if(node==root.let[0]) return;
//cout<<node->last<<endl;
//cout<<node->par->last<<endl;
anc[node][0] = node->par;
FORi(i,1,25){
anc[node][i] = anc[anc[node][i-1]][i-1];
if(anc[node][i]==root.let[0]) break;
}
}
trie* ancest(trie* node, int x){
int ind=0;
while(x){
if(x%2==1) node = anc[node][ind];
ind++;
x/=2;
}
return node;
}
void Init() {
//cout<<"INITED\n";
root.let[0] = new trie('a', 0, &root);
history.push_back(root.let[0]);
prepr(root.let[0]);
}
void TypeLetter(char L) {
history.push_back(history.back()->add(L));
prepr(history.back());
}
void UndoCommands(int U) {
history.push_back(history[history.size()-U-1]);
}
char GetLetter(int P) {
//FOA(v,history) cout<<v<<" "<<v->last<<endl;
int up = history.back()->s - P-1;
return ancest(history.back(), up)->last;
}
