#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);
}
} st[N];
int cur[N];
int t;
void Init() {
st[0].build();
}
void TypeLetter(char L) {
st[t].upd(cur[t]++, L - 'a');
cur[t + 1] = cur[t];
st[t + 1] = st[t++];
}
void UndoCommands(int U) {
cur[t] = cur[t + 1] = cur[t - U - 1];
st[t++] = st[t + 1] = st[t - U - 1];
}
char GetLetter(int P) {
return 'a' + st[t].qry(P);
}
