#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct Trie {
char c;
int len;
Trie *nxt[4];
Trie(char cur = '.'): c(cur), len(0) {
for (int i = 0; i < 4; i++) nxt[i] = nullptr;
};
};
vector<Trie*> ver;
int cnt = 0;
Trie *cur, *pre;
void Init() {
cur = new Trie();
cnt++;
function<void(Trie*, int)> build = [&](Trie *cur, int depth) {
if (depth < 0) return;
for (int i = 0; i < 4; i++) {
cur->nxt[i] = new Trie();
build(cur->nxt[i], depth - 2);
}
cnt += 4;
};
build(cur, 18);
ver.pb(cur);
}
void TypeLetter(char L) {
cur = new Trie();
cnt++;
pre = ver.back();
ver.pb(cur);
for (int i = 18; i >= 0; i -= 2) {
cur->len = pre->len;
int tar = cur->len++;
for (int j = 0; j < 4; j++) {
cur->nxt[j] = pre->nxt[j];
}
int dest = ((tar >> i) & 3);
pre = cur->nxt[dest];
cur->nxt[dest] = new Trie();
cur = cur->nxt[dest];
cnt++;
}
cur->c = L;
}
void UndoCommands(int U) {
cur = new Trie();
cnt++;
int ptr = (int)(ver.size()) - 1 - U;
for (int i = 0; i < 4; i++) {
cur->nxt[i] = ver[ptr]->nxt[i];
}
cur->len = ver[ptr]->len;
ver.pb(cur);
}
char GetLetter(int P) {
cur = ver.back();
for (int i = 18; i >= 0; i -= 2) {
int dest = ((P >> i) & 3);
cur = cur->nxt[dest];
}
// cerr << cnt << endl;
return cur->c;
}
