#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
using namespace std;
#define ll int
// TODO: global variables can be declared here
struct info{
ll lver,rver;
};
struct SEG{
vector<info>seg[524288*4-200000];
ll vernochar[1000001];
ll versionofcommand[1000001];
vector<char>opt[1000001];
void build(ll l, ll r, ll id){
if(l==r){
seg[id].push_back({0,0});
}
else{
ll mid=(l+r)>>1;
build(l,mid,id*2);
build(mid+1,r,id*2+1);
seg[id].push_back({0,0});
}
}
char qry(ll version, ll ql, ll l, ll r, ll id){
if(l==r){
return opt[ql][version-1];
}
else{
ll mid=(l+r)>>1;
if(ql<=mid){
return qry(seg[id][version].lver,ql,l,mid,id*2);
}
else{
return qry(seg[id][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].push_back({0,0});
opt[ul].push_back(app);
}
else{
ll mid=(l+r)>>1;
if(ul<=mid){
upd(seg[id][version].lver,ul,l,mid,app,id*2);
ll siz=seg[id*2].size()-1;
seg[id].push_back({siz,seg[id][version].rver});
}
else{
upd(seg[id][version].rver,ul,mid+1,r,app,id*2+1);
ll siz=seg[id*2+1].size()-1;
seg[id].push_back({seg[id][version].lver,siz});
}
}
}
};
SEG st;
ll curcom=1;
void Init() {
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].size()-1]=k+1;
st.versionofcommand[curcom]=st.seg[1].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);
}
