#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() {
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) {
int ptr = (int)(ver.size()) - 1 - U;
ver.pb(ver[ptr]);
}
char GetLetter(int P) {
cur = ver.back();
while (cur->len != 1) {
if (P < cur->lptr->len) {
cur = cur->lptr;
} else {
P -= cur->lptr->len;
cur = cur->rptr;
}
}
return cur->c;
}
