#include <bits/stdc++.h>
using namespace std;
constexpr int LG = 20, SZ = 1 << LG, NODES = SZ * (LG + 3);
int Root[SZ], Len[SZ], L[NODES], R[NODES], V[NODES], C, Pos;
void Init(int node, int s, int e){
if(s == e) return;
int m = (s + e) / 2;
L[node] = ++C; R[node] = ++C;
Init(L[node], s, m);
Init(R[node], m+1, e);
}
void Update(int prv, int now, int s, int e, int x, int v){
if(s == e){ V[now] = v; return; }
int m = (s + e) / 2;
if(x <= m){
L[now] = ++C; R[now] = R[prv];
Update(L[prv], L[now], s, m, x, v);
}
else{
L[now] = L[prv]; R[now] = ++C;
Update(R[prv], R[now], m+1, e, x, v);
}
}
char Get(int node, int s, int e, int x){
if(s == e) return V[node];
int m = (s + e) / 2;
if(x <= m) return Get(L[node], s, m, x);
else return Get(R[node], m+1, e, x);
}
void Print(int node, int s, int e, int sz){
if(s >= sz) return;
if(s == e){ cout << char(V[node]); return; }
int m = (s + e) / 2;
Print(L[node], s, m, sz);
Print(R[node], m+1, e, sz);
}
void Init(){
Root[0] = ++C;
Init(Root[0], 0, SZ-1);
}
void TypeLetter(char c){
Root[++Pos] = ++C; Len[Pos] = Len[Pos-1] + 1;
Update(Root[Pos-1], Root[Pos], 0, SZ-1, Len[Pos-1], c);
}
void UndoCommands(int k){
Root[++Pos] = ++C; Len[Pos] = Len[Pos-k-1];
L[Root[Pos]] = L[Root[Pos-k-1]];
R[Root[Pos]] = R[Root[Pos-k-1]];
}
char GetLetter(int k){
return Get(Root[Pos], 0, SZ-1, k);
}
