#include <bits/stdc++.h>
#define lp(i,a,b) for(int i = a; i <b;i++)
#define ff first
#define ss second
#define pb push_back
#define mk make_pair
#define sz size()
#define debug printf
#define ll long long
#define pii pair<int,int>
const int MAXN = 1e6+10;
using namespace std ;
struct Seg
{
vector<int> e , d , soma ;
int m(int l, int r) { return (l+r)>>1 ; }
int create()
{
e.pb(0) ;
d.pb(0) ;
soma.pb(0) ;
return (int)(e.sz) - 1 ;
}
int create_and_copy(int x)
{
e.pb(e[x]) ;
d.pb(d[x]) ;
soma.pb(soma[x]) ;
return (int)(e.sz) - 1 ;
}
int upd(int pos,int l, int r, int idx)
{
int brandNew = create_and_copy(pos) ;
if( l == r )
{
soma[brandNew] = 1 ;
return brandNew ;
}
int aux ;
if( idx <= m(l,r) )
{
aux = upd( e[brandNew] , l , m(l,r) , idx ) ;
e[brandNew] = aux ;
}
else
{
aux = upd(d[brandNew] ,m(l,r)+1, r, idx ) ;
d[brandNew] = aux ;
}
soma[brandNew] = soma[ e[brandNew] ] + soma[ d[brandNew] ] ;
return brandNew ;
}
int binarySearch(int pos, int l, int r, int tot )
{
if( l == r ) return l ;
if( soma[e[pos]] >= tot ) return binarySearch(e[pos],l,m(l,r),tot) ;
return binarySearch(d[pos],m(l,r)+1, r, tot - soma[e[pos]]) ;
}
void init()
{
e.clear() ;
d.clear() ;
soma.clear() ;
}
} ;
int curId ;
int version[MAXN] ;
Seg seg ;
char letter[MAXN] ;
void Init()
{
seg.init() ;
version[0] = 0 ;
seg.create() ;
curId = 0;
}
void TypeLetter(char L) {
curId ++ ;
version[curId] = seg.upd( version[curId-1] , 1 , MAXN , curId ) ;
letter[curId] = L ;
}
void UndoCommands(int U) {
curId ++ ;
version[curId] = version[curId - U-1 ] ;
}
char GetLetter(int P) {
return letter[ seg.binarySearch(version[curId],1,MAXN,P+1) ] ;
}
