#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;
int cnt = 0;
Trie *cur, *pre;
void Init() {
cur = new Trie();
cnt++;
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);
cnt += 2;
};
build(cur, 19);
ver.pb(cur);
}
void TypeLetter(char L) {
cur = new Trie();
cnt++;
pre = ver.back();
ver.pb(cur);
for (int i = 19; i >= 0; i--) {
cur->len = pre->len;
int tar = cur->len++;
cur->lptr = pre->lptr;
cur->rptr = pre->rptr;
if (!bool(tar & (1 << i))) {
pre = cur->lptr;
cur->lptr = new Trie();
cur = cur->lptr;
} else {
pre = cur->rptr;
cur->rptr = new Trie();
cur = cur->rptr;
}
cnt++;
}
cur->c = L;
}
void UndoCommands(int U) {
cur = new Trie();
cnt++;
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) {
cur = ver.back();
for (int i = 19; i >= 0; i--) {
if (!bool(P & (1 << i))) {
cur = cur->lptr;
} else {
cur = cur->rptr;
}
}
// cerr << cnt << endl;
return cur->c;
}
