#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+1;
struct item {
char val;
item *l, *r;
item(char val, item *l, item *r) : val(val), l(l), r(r) {}
};
item* newson(char val) { return new item(val, nullptr, nullptr); }
item* newpar(char val, item *l, item *r) { return new item(val, l, r); }
int step;
item* ver[N];
int sz[N];
item* build(int l = 0, int r = N) {
if(l == r) return newson('0');
int m = l + r >> 1;
return newpar(0, build(l, m), build(m+1, r));
}
char query(int pos, item* p, int l = 0, int r = N) {
if(l == r) return p->val;
int m = l + r >> 1;
if(pos <= m) return query(pos, p->l, l, m);
else return query(pos, p->r, m+1, r);
}
item* update(int pos, char val, item *p, int l = 0, int r = N) {
if(l == r) return newson(val);
int m = l + r >> 1;
if(pos <= m) return newpar(0, update(pos, val, p->l, l, m), p->r);
else return newpar(0, p->l, update(pos, val, p->r, m+1, r));
}
void Init() {
ver[0] = build();
}
void TypeLetter(char L) {
ver[step+1] = update(sz[step+1] = sz[step], L, ver[step]);
sz[++step]++;
}
void UndoCommands(int U) {
ver[step+1] = ver[step-U];
sz[step+1] = sz[step-U];
step++;
}
char GetLetter(int P) {
return query(P, ver[step]);
}
