#include<bits/stdc++.h>
using namespace std;
#define ll long long
// TODO: global variables can be declared here
struct info{
char c;
ll lver,rver;
};
struct node{
vector<info>ver;
};
struct SEG{
vector<node>seg;
ll vernochar[1000005];
ll versionofcommand[1000005];
void init(ll n){
seg.resize(4*n+5);
}
void build(ll l, ll r, ll id){
if(l==r){
seg[id].ver.push_back({'-',0,0});
}
else{
ll mid=(l+r)>>1;
build(l,mid,id*2);
build(mid+1,r,id*2+1);
seg[id].ver.push_back({'-',0,0});
}
}
char qry(ll version, ll ql, ll l, ll r, ll id){
if(l==r){
return seg[id].ver[version].c;
}
else{
ll mid=(l+r)>>1;
if(ql<=mid){
return qry(seg[id].ver[version].lver,ql,l,mid,id*2);
}
else{
return qry(seg[id].ver[version].rver,ql,mid+1,r,id*2+1);
}
}
}
void upd(ll version, ll ul, ll l, ll r, char app, ll id){
if(l==r){
seg[id].ver.push_back({app,0,0});
}
else{
ll mid=(l+r)>>1;
if(ul<=mid){
upd(seg[id].ver[version].lver,ul,l,mid,app,id*2);
ll siz=seg[id*2].ver.size()-1;
seg[id].ver.push_back({'-',siz,seg[id].ver[version].rver});
}
else{
upd(seg[id].ver[version].rver,ul,mid+1,r,app,id*2+1);
ll siz=seg[id*2+1].ver.size()-1;
seg[id].ver.push_back({'-',seg[id].ver[version].lver,siz});
}
}
}
};
SEG st;
ll curcom=1;
void Init() {
st.init(1000000);
st.build(1,1000000,1);
st.vernochar[0]=0;
st.versionofcommand[0]=0;
}
void TypeLetter(char L){
// TODO: implementation
ll acccom=curcom-1;
ll lol=st.versionofcommand[acccom];
ll k=st.vernochar[lol];
st.upd(lol,k+1,1,1000000,L,1);
st.vernochar[st.seg[1].ver.size()-1]=k+1;
st.versionofcommand[curcom]=st.seg[1].ver.size()-1;
curcom++;
}
void UndoCommands(int U){
// TODO: implementation
ll acccom=curcom-U-1;
st.versionofcommand[curcom]=st.versionofcommand[acccom];
curcom++;
}
char GetLetter(int P){
// TODO: implementation
ll version=st.versionofcommand[curcom-1];
// cout<<version<<'\n';
P++;
return st.qry(version,P,1,1000000,1);
}
