#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
int lc[N * 27], rc[N * 27];
char st[N * 27];
int sz[N], rt[N], cur = 1;
int idx = 0;
int upd(int p, int l, int r, int i, char x){
int nd = cur++;
if(l == r){
st[nd] = x;
}else{
int m = (l + r) / 2;
lc[nd] = lc[p], rc[nd] = rc[p];
if(i <= m) lc[nd] = upd(lc[nd], l, m, i, x);
else rc[nd] = upd(rc[nd], m + 1, r, i, x);
}
return nd;
}
char qry(int p, int l, int r, int i){
if(l == r){
return st[p];
}else{
int m = (l + r) / 2;
if(i <= m) return qry(lc[p], l, m, i);
else return qry(rc[p], m + 1, r, i);
}
}
void Init(){
}
void TypeLetter(char L){
rt[idx + 1] = upd(rt[idx], 0, 1000000, sz[idx], L);
sz[idx + 1] = sz[idx] + 1;
idx++;
}
void UndoCommands(int U){
rt[idx + 1] = rt[idx - U];
sz[idx + 1] = sz[idx - U];
idx++;
}
char GetLetter(int P){
return qry(rt[idx], 0, 1000000, P);
}
