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