#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x).size()
struct trie {
int next[26], sz;
char ch;
vector<int> up;
trie() {
memset(next, -1, sizeof(next));
ch=0, sz=0;
}
};
vector<trie*> tries;
vector<int> empls;
void Init() {
tries.pb(new trie());
empls.pb(0);
}
void TypeLetter(char L) {
int act = empls.back();
if (tries[act]->next[L-'a']!=-1) {
empls.pb(tries[act]->next[L-'a']);
return;
}
tries[act]->next[L-'a'] = sz(tries);
tries.pb(new trie()), empls.pb(sz(tries)-1); tries.back()->ch=L, tries.back()->sz=tries[act]->sz+1;
trie *cur=tries.back();
cur->up.pb(act);
for (int j=1; j<20; j++) {
if (sz(tries[cur->up[j-1]]->up)<j) break;
cur->up.pb(tries[cur->up[j-1]]->up[j-1]);
}
}
void UndoCommands(int U) {
empls.pb(empls[sz(empls)-U-1]);
}
char GetLetter(int P) {
int act=empls.back();
int k=tries[act]->sz-P-1;
for (int j=0; j<20; j++) {
if ((k&(1<<j))) {
act=tries[act]->up[j];
}
}
return tries[act]->ch;
}
