#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
struct node {
int val;
node *left, *right;
node() : left(NULL), right(NULL) { };
node(const int &x) : val(x), left(NULL), right(NULL) { };
node(node* l, node* r) : left(l), right(r) { };
};
struct Persistent_Segment_Tree {
node *root;
Persistent_Segment_Tree() : root(NULL) { };
node* upd(node* v, int l, int r, int u, int x) {
if (l == r) return new node(x);
int m = l + r >> 1;
if (u <= m) return new node(upd(v->left, l, m, u, x), v->right);
else return new node(v->left, upd(v->right, m + 1, r, u, x));
}
node* build(node *v, int l, int r) {
if (l == r) return new node;
int m = l + r >> 1;
return new node(build(v->left, l, m), build(v->right, m + 1, r));
}
int qry(node* &v, int l, int r, int u) {
if (l == r) return v->val;
int m = l + r >> 1;
if (u <= m) return qry(v->left, l, m, u);
return qry(v->right, m + 1, r, u);
}
void build() {
root = build(root, 0, N - 1);
}
void upd(int u, int x) {
root = upd(root, 0, N - 1, u, x);
}
int qry(int u) {
return qry(root, 0, N - 1, u);
}
};
vector<Persistent_Segment_Tree> st;
int cur[N];
void Init() {
st.push_back(Persistent_Segment_Tree());
st[0].build();
}
void TypeLetter(char L) {
st.back().upd(cur[st.size() - 1]++, L - 'a');
cur[st.size()] = cur[st.size() - 1];
st.push_back(st.back());
}
void UndoCommands(int U) {
cur[st.size() - 1] = cur[st.size()] = cur[st.size() - U - 2];
st.back() = st[st.size() - U - 2];
st.push_back(st.back());
}
char GetLetter(int P) {
return 'a' + st.back().qry(P);
}
