#include <bits/stdc++.h>
using namespace std;
struct node {
node *par[22] = {};
node *child[26] = {};
int dep = 0;
node() {}
} *roots[1000005];
int cround = 0;
void Init() {
roots[0] = new node();
cround = 0;
}
void TypeLetter(char L) {
L -= 'a';
if(roots[cround]->child[L]) {roots[cround+1] = roots[cround]->child[L];}
else {
roots[cround]->child[L] = new node();
roots[cround]->child[L]->par[0] = roots[cround];
for(int i=0;i<21;i++) {
if(roots[cround]->child[L]->par[i]->par[i]) {
roots[cround]->child[L]->par[i+1] = roots[cround]->child[L]->par[i]->par[i];
} else break;
}
roots[cround]->child[L]->dep = roots[cround]->dep + 1;
roots[cround+1] = roots[cround]->child[L];
}
cround++;
}
void UndoCommands(int U) {
roots[cround+1] = roots[cround - U];
cround++;
}
node *getpar(node * cur, int res) {
if(!res) return cur;
if(res > cur->dep) exit(1);
for(int i=20;i>=0;i--) if((1 << i) & res) cur = cur->par[i];
return cur;
}
char GetLetter(int P) {
auto olderpar = getpar(roots[cround], roots[cround]->dep - P), newerpar = getpar(roots[cround], roots[cround]->dep-P-1);
for(int i=0;i<26;i++) {
if(olderpar->child[i] == newerpar) {
return i+'a';
}
}
exit(1);
}
