#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
struct node {
char c;
node *left, *right;
node() : left(NULL), right(NULL) { };
node(const char &x) : c(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, const char &x) {
if (l == r) return new node(x);
if (!v) v = new node;
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));
}
char qry(node* &v, int l, int r, int u) {
if (l == r) return v->c;
int m = l + r >> 1;
if (u <= m) return qry(v->left, l, m, u);
return qry(v->right, m + 1, r, u);
}
} st[N];
int cur[N];
int t;
void Init() {
}
void TypeLetter(char L) {
st[t].root = st[t + 1].root = st[t].upd(st[t].root, 0, N - 1, cur[t]++, L);
cur[t + 1] = cur[t];
t++;
}
void UndoCommands(int U) {
cur[t] = cur[t + 1] = cur[t - U - 1];
st[t].root = st[t + 1].root = st[t - U - 1].root;
t++;
}
char GetLetter(int P) {
return st[t].qry(st[t].root, 0, N - 1, P);
}
