#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 vector<int> vi;
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)
static int last_id=0;
struct trie{
trie* let[26];
int id;
trie* par;
char last;
int s=0;
trie(){
FOR(i,26) let[i] = nullptr;
id = last_id++;
}
trie(char x, int ns, trie* p){
id = last_id++;
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;
#define LAY 22
trie* anc[1001000][LAY] = {};
//unordered_map<trie*, vector<trie*> > anc;
trie root;
//bool used[1001000];
void prepr(trie* node){
//cout<<node->id<<endl;
if(node==root.let[0]) return;
//cout<<node->last<<endl;
//cout<<node->par->last<<endl;
anc[node->id][0] = node->par;
FORi(i,1,LAY){
if(anc[anc[node->id][i-1]->id][i-1]==nullptr) prepr(anc[node->id][i-1]);
anc[node->id][i] = anc[anc[node->id][i-1]->id][i-1];
}
//used[node->id] = true;
}
trie* ancest(trie* node, int x){
int ind=0;
if(x>=node->s) return root.let[0];
while(x){
if(x%2==1){
if(anc[node->id][ind]==nullptr) prepr(node);
node = anc[node->id][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]);
FOR(i,LAY) anc[root.let[0]->id][i] = root.let[0];
//prepr(root.let[0]);
}
void TypeLetter(char L) {
history.push_back(history.back()->add(L));
//if(!used[history.back()->id])
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;
}
