#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt")
using namespace std;
#define len(x) (int) x.size()
using i32 = int32_t;
template<typename T>
using vec = vector<T>;
struct node {
int cnt;
int left, right;
explicit node(int val) : left(-1), right(-1) {
if (val != -1) cnt = -val;
else cnt = 0;
}
node() = default;
};
const int maxNodes = 1e8 + 5;
node nodes[maxNodes];
int cnt_nodes = 0;
void fetch(int id) {
if (id == -1) return;
nodes[id].cnt = 0;
if (nodes[id].left != -1) nodes[id].cnt += (nodes[nodes[id].left].cnt < 0) + max(0, nodes[nodes[id].left].cnt);
if (nodes[id].right != -1) nodes[id].cnt += (nodes[nodes[id].right].cnt < 0) + max(0, nodes[nodes[id].right].cnt);
}
int add_node(int x) {
nodes[cnt_nodes] = node(x);
return cnt_nodes++;
}
int build(int l, int r) {
if (l == r) {
return add_node(-1);
}
int m = (l + r) / 2;
int new_root = add_node(-1);
int id = build(l, m);
nodes[new_root].left = id;
id = build(m + 1, r);
nodes[new_root].right = id;
fetch(new_root);
return new_root;
}
int update(int v, int l, int r, int pos, int val) {
if (l == r) {
return add_node(val);
}
int m = (l + r) / 2;
int new_node = add_node(-1);
if (pos <= m) {
int left = update(nodes[v].left, l, m, pos, val);
nodes[new_node].left = left;
nodes[new_node].right = nodes[v].right;
} else {
int right = update(nodes[v].right, m + 1, r, pos, val);
nodes[new_node].right = right;
nodes[new_node].left = nodes[v].left;
}
fetch(new_node);
return new_node;
}
int get(int v, int l, int r, int pos) {
if (l == r) {
return -nodes[v].cnt;
}
int m = (l + r) / 2;
if (pos <= m) {
return get(nodes[v].left, l, m, pos);
} else {
return get(nodes[v].right, m + 1, r, pos);
}
}
const int maxN = 1e6 + 5;
vec<int> roots;
void Init() {
roots.push_back(build(0, maxN));
}
void TypeLetter(char L) {
int last = roots.back();
int new_n = update(last, 0, maxN, nodes[last].cnt, L);
roots.push_back(new_n);
}
void UndoCommands(i32 U) {
int pr = roots[len(roots) - U - 1];
roots.push_back(pr);
}
char GetLetter(i32 P) {
return get(roots.back(), 0, maxN, P);
}
