#include <bits/stdc++.h>
using namespace std;
#define pb push_back
int flog2(int x) {
return 31 - __builtin_clz(x);
}
bool ispow2(int x) {
return (x == (1 << flog2(x)));
}
struct Trie {
char c;
int len;
Trie *lptr, *rptr;
Trie(char cur = '.'): c(cur), len((cur != '.')), lptr(nullptr), rptr(nullptr) {};
};
vector<Trie*> ver;
Trie *cur, *pre;
void Init() {
// 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);
ver.pb(nullptr);
}
void TypeLetter(char L) {
cur = new Trie();
pre = ver.back();
ver.pb(cur);
while (pre != nullptr) {
cur->len = pre->len + 1;
if (ispow2(pre->len)) {
cur->lptr = pre;
cur->rptr = new Trie(L);
return;
}
cur->lptr = pre->lptr;
cur->rptr = new Trie();
cur = cur->rptr;
pre = pre->rptr;
}
cur->c = L;
cur->len = 1;
}
void UndoCommands(int U) {
cur = new Trie();
int ptr = (int)(ver.size()) - 1 - U;
if (ptr == 0) {
cur = nullptr;
} else {
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();
while (cur->len != 1) {
// cerr << cur->len << ' ' << cur->c << endl;
if (P < cur->lptr->len) {
cur = cur->lptr;
} else {
P -= cur->lptr->len;
cur = cur->rptr;
}
}
return cur->c;
}
