#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;
};
vector<info>seg[1048575];
ll vernochar[1000001];
ll versionofcommand[1000001];
vector<char>opt[1000001];
void build(ll l, ll r, ll id){
if(l==r){
return;
}
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){
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;
if(l==mid){
siz=opt[ul].size();
}
else{
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;
if(mid+1==r){
siz=opt[ul].size();
}
else{
siz=seg[id*2+1].size()-1;
}
seg[id].push_back({seg[id][version].lver,siz});
}
}
}
ll curcom=1;
void Init() {
build(1,1000000,1);
vernochar[0]=0;
versionofcommand[0]=0;
}
void TypeLetter(char L){
// TODO: implementation
ll acccom=curcom-1;
ll lol=versionofcommand[acccom];
ll k=vernochar[lol];
upd(lol,k+1,1,1000000,L,1);
vernochar[seg[1].size()-1]=k+1;
versionofcommand[curcom]=seg[1].size()-1;
curcom++;
}
void UndoCommands(int U){
// TODO: implementation
ll acccom=curcom-U-1;
versionofcommand[curcom]=versionofcommand[acccom];
curcom++;
}
char GetLetter(int P){
// TODO: implementation
ll version=versionofcommand[curcom-1];
// cout<<version<<'\n';
P++;
return qry(version,P,1,1000000,1);
}
