#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
struct SegTreeNode {
char val = '0';
SegTreeNode* l = nullptr;
SegTreeNode* r = nullptr;
};
namespace mempool {
//SegTreeNode pool[15000005];
//int idx = 0;
SegTreeNode* new_node() {
return new SegTreeNode;
//return pool + idx++;
}
}
int roots = 0;
int depth[1000005];
SegTreeNode* root[1000005];
std::vector<int> stk;
inline char get_val(SegTreeNode* node) {
if (!node) {
return 0;
}
return node->val;
}
inline SegTreeNode* get_l(SegTreeNode* node) {
if (!node) {
return nullptr;
}
return node->l;
}
inline SegTreeNode* get_r(SegTreeNode* node) {
if (!node) {
return nullptr;
}
return node->r;
}
SegTreeNode* update(SegTreeNode* root, int l, int r, int pos, char val) {
SegTreeNode* ret = mempool::new_node();
ret->l = get_l(root);
ret->r = get_r(root);
if (l == r) {
ret->val = val;
return ret;
}
int m = (l+r)>>1;
if (pos <= m) {
ret->l = update(ret->l, l, m, pos, val);
}
else {
ret->r = update(ret->r, m+1, r, pos, val);
}
return ret;
}
// this assumes that the path in question exists, which should always be the case
char query(SegTreeNode* root, int l, int r, int pos) {
if (l == r) {
return root->val;
}
int m = (l+r)>>1;
if (pos <= m) {
return query(root->l, l, m, pos);
}
else {
return query(root->r, m+1, r, pos);
}
}
void Init() {
roots = 1;
root[0] = mempool::new_node();
depth[0] = 0;
stk.emplace_back(0);
}
void TypeLetter(char L) {
int old_root = stk.back();
int new_root = roots;
depth[new_root] = depth[old_root] + 1;
root[new_root] = update(root[old_root], 1, 1000000, depth[new_root], L);
stk.emplace_back(new_root);
++roots;
//std::cout << stk.size() << "\n";
}
void UndoCommands(int U) {
int curr_state = stk.back();
int new_state = stk[stk.size()-1-U];
stk.pop_back();
stk.emplace_back(curr_state);
stk.emplace_back(new_state);
//std::cout << stk.size() << "\n";
}
char GetLetter(int P) {
int curr_state = stk.back();
//std::cout << depth[curr_state] << " " << P+1 << "\n";
return query(root[curr_state], 1, 1000000, P+1);
}
