#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct Trie {
char c;
int len;
Trie *lptr, *rptr;
Trie(char cur = '.'): c(cur), len(0), lptr(nullptr), rptr(nullptr) {};
};
vector<Trie*> ver;
void Init() {
Trie *cur = new Trie();
function<void(Trie*, int)> build = [&](Trie *cur, int depth) {
if (depth == -1) return;
cur->lptr = new Trie(); build(cur->lptr, depth - 1);
cur->rptr = new Trie(); build(cur->rptr, depth - 1);
};
build(cur, 19);
ver.pb(cur);
}
void TypeLetter(char L) {
Trie *cur = new Trie();
Trie *prev = ver.back();
ver.pb(cur);
for (int i = 19; i >= 0; i--) {
cur->len = prev->len;
int tar = cur->len++;
cur->lptr = prev->lptr;
cur->rptr = prev->rptr;
if (!bool(tar & (1 << i))) {
prev = cur->lptr;
cur->lptr = new Trie();
cur = cur->lptr;
} else {
prev = cur->rptr;
cur->rptr = new Trie();
cur = cur->rptr;
}
}
cur->c = L;
}
void UndoCommands(int U) {
Trie *cur = new Trie();
int ptr = (int)(ver.size()) - 1 - U;
cur->lptr = ver[ptr]->lptr;
cur->rptr = ver[ptr]->rptr;
cur->len = ver[ptr]->len;
ver.pb(cur);
}
char GetLetter(int P) {
Trie *cur = ver.back();
for (int i = 19; i >= 0; i--) {
if (!bool(P & (1 << i))) {
cur = cur->lptr;
} else {
cur = cur->rptr;
}
}
return cur->c;
}
