#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
const int MAXN = 1e6;
vector<int> sum,e,d,rz;
int tot = 0;
string s;
int create(){
sum.push_back(0);
e.push_back(0);
d.push_back(0);
return sz(sum)-1;
}
int update(int node, int l, int r, int i){
int novo = create();
sum[novo] = sum[node];
e[novo] = e[node];
d[novo] = d[node];
if(l == r){
sum[novo]++;
return novo;
}
int mid = (l+r)/2;
if(i <= mid){
int aux = update(e[novo], l, mid, i);
e[novo] = aux;
}else{
int aux = update(d[novo], mid+1, r, i);
d[novo] = aux;
}
sum[novo] = sum[e[novo]]+sum[d[novo]];
return novo;
}
int query(int node, int l, int r, int x){
if(l == r)return l;
int mid = (l+r)/2;
if(sum[e[node]] >= x)return query(e[node],l,mid,x);
return query(d[node],mid+1,r,x-sum[e[node]]);
}
void Init() {
rz.push_back(create());
}
void TypeLetter(char c) {
tot++; s.push_back(c);
rz.push_back(update(rz.back(), 1, MAXN, tot));
}
void UndoCommands(int u) {
int novo = create();
sum[novo] = sum[ rz[sz(rz)-u-1] ];
e[novo] = e[ rz[sz(rz)-u-1] ];
d[novo] = d[ rz[sz(rz)-u-1] ];
rz.push_back(novo);
}
char GetLetter(int pos) {
return s[query(rz.back(), 1, MAXN, pos+1)-1];
}
