#include <bits/stdc++.h>
#define MAX 22000000
const int lim = 1e6+7;
char valor[MAX];
int left[MAX],right[MAX];
int cur=3;
int alocar(void){
return cur++;
}
void copia(int a,int b){
left[a]=left[b];
right[a]=right[b];
valor[a]=valor[b];
}
char get(int t,int v,int la=0,int ra=lim){
if(la==ra){
return valor[v];
}
int m = (la+ra)/2;
if(t<=m){///Left
return get(t,left[v],la,m);
}else {///Right
return get(t,right[v],m+1,ra);
}
}
void update(int t,char ch,int v,int la=0,int ra=lim){
if(la==ra){
valor[v]=ch;
return;
}
int m = (la+ra)/2;
if(t<=m){///Left
int prev = left[v];
left[v]=alocar();
copia(left[v],prev);
update(t,ch,left[v],la,m);
}else {///Right
int prev = right[v];
right[v]=alocar();
copia(right[v],prev);
update(t,ch,right[v],m+1,ra);
}
}
std::vector<int> updates;
std::vector<int> size;
void Init() {
updates.push_back(alocar());
size.push_back(0);
}
void TypeLetter(char L) {
int sz = size.back();
size.push_back(sz+1);
updates.push_back(alocar());
copia(updates.back(),updates[updates.size()-2]);
update(sz,L,updates.back());
}
void UndoCommands(int U) {
int cord = updates.size()-U-1;
size.push_back(size[cord]);
updates.push_back(alocar());
copia(updates.back(),updates[cord]);
}
char GetLetter(int P) {
return get(P,updates.back());
}
