#include <bits/stdc++.h>
using namespace std;
const int nx=1e6+5;
int cnt[nx], t;
struct persist
{
struct node
{
node *l, *r;
char c=' ';
node(char c): l(0), r(0), c(c){}
};
typedef node* pnode;
pnode rt[nx];
void build(int l, int r, pnode &t)
{
t=new node(' ');
if (l==r) return;
int md=(l+r)/2;
build(l, md, t->l);
build(md+1, r, t->r);
}
void update(int l, int r, int idx, char ch, pnode &t, pnode k)
{
t=new node(*k);
if (l==r) return void(t->c=ch);
int md=(l+r)/2;
if (idx<=md) update(l, md, idx, ch, t->l, k->l);
else update(md+1, r, idx, ch, t->r, k->r);
}
char query(int l, int r, int idx, pnode t)
{
if (l==r) return t->c;
int md=(l+r)/2;
if (idx<=md) return query(l, md, idx, t->l);
return query(md+1, r, idx, t->r);
}
} s;
void Init() {
s.build(1, nx-1, s.rt[0]);
}
void TypeLetter(char L) {
t++; cnt[t]=cnt[t-1]+1;
s.update(1, nx-1, cnt[t], L, s.rt[t], s.rt[t-1]);
}
void UndoCommands(int U) {
t++;
cnt[t]=cnt[max(t-U-1, 0)];
s.rt[t]=s.rt[max(t-U-1, 0)];
}
char GetLetter(int P) {
return s.query(1, nx-1, P+1, s.rt[t]);
}
