#include<bits/stdc++.h>
using namespace std;
#define pb push_back
struct node{
char c;
int lc, rc;
};
vector<node> st;
vector<int> roots;
int nxtind[1000010];
int cntop=0;
void Build(int v, int l, int r){
if(l>r)return;
if(l==r){
st.pb({0, -1, -1});
return;
}
int mid=l+r>>1;
st.pb({0, 2*v+1, 2*v+2});
Build(2*v+1, l, mid);
Build(2*v+2, mid+1, r);
}
void Add(int v, int l, int r, char c){
if(l==r){
st.pb({c, -1, -1});
return;
}
int mid=l+r>>1;
st.pb(st[v]);
if(mid>=nxtind[cntop]){
st[st.size()-1].lc=st.size();
Add(st.size(), l, mid, c);
}
else{
st[st.size()-1].rc=st.size();
Add(st.size(), mid+1, r, c);
}
}
char Get(int v, int l, int r, int ind){
if(l==r)return st[v].c;
int mid=l+r>>1;
if(ind<=mid)return Get(st[v].lc, l, mid, ind);
return Get(st[v].rc, mid+1, r, ind);
}
void TypeLetter(char c) {
int nw=st.size();
Add(roots.back(), 0, 1000010, c);
roots.pb(nw);
cntop++;
nxtind[cntop]=nxtind[cntop-1]+1;
}
void UndoCommands(int num) {
roots.pb(roots[roots.size()-num-1]);
cntop++;
nxtind[cntop]=nxtind[cntop-num-1];
}
char GetLetter(int ind) {
return Get(roots.back(), 0, 1000010, ind);
}
void Init() {
Build(0, 0, 1000010);
roots.pb(0);
nxtind[0]=0;
}
