#include <bits/stdc++.h>
using namespace std ;
const int N = 1e6+2 ;
int L[ 20*N ], R[ 20*N ], lazy [ 20*N ], sum [ 20*N ] ;
int lst[N], nec[N], q, last = 0, cur = 0;
char let[N] ;
int nodeG = 0;
int visit[N] ;
struct info {
int l, r, nod ;
};
info fll ( int li, int ri, int node ) {
info x = {li,ri,node} ;
return x ;
}
int build ( info i ) {
if ( i.l == i.r )
return i.nod ;
info x = fll ( i.l, (i.l+i.r)/2, ++nodeG ) ;
L[i.nod] = build ( x ) ;
x = fll ( (i.l+i.r)/2+1, i.r, ++nodeG ) ;
R[i.nod] = build ( x ) ;
return i.nod ;
}
void propagate ( info i ) {
if ( lazy[i.nod] == -1 ) return ;
if ( L[i.nod] ) lazy[L[i.nod]] = lazy[i.nod] ;
if ( R[i.nod] ) lazy[R[i.nod]] = lazy[i.nod] ;
sum[i.nod] = lazy[i.nod]*(i.r-i.l+1) ;
lazy[i.nod] = -1 ;
}
void update ( info i, int a, int b, int val ) {
if ( a > b ) return ;
propagate ( i ) ;
int mid = (i.l+i.r)/2 ;
if ( i.l == a && i.r == b ) {
lazy[i.nod] = val ;
propagate ( i ) ;
return ;
}
info x = fll(i.l,mid,L[i.nod]) ;
info x2 = fll(mid+1, i.r, R[i.nod]) ;
if ( b <= mid ) update ( x, a, b, val ) ;
else if ( a > mid ) update ( x2, a, b, val ) ;
else {
update (x, a, mid, val) ;
update (x2, mid+1, b, val );
}
sum[i.nod] = sum[L[i.nod]] + sum[R[i.nod]] ;
}
int query ( info i, int a, int b ) {
if ( a > b ) return 0 ;
propagate(i) ;
if ( i.l == a && i.r == b ) return sum[i.nod] ;
int mid = (i.l+i.r)/2 ;
info x = fll(i.l,mid,L[i.nod]) ;
info x2 = fll(mid+1, i.r, R[i.nod]) ;
if ( b <= mid ) return query ( x, a, b ) ;
if ( a > mid ) return query ( x2, a, b ) ;
return query (x, a, mid) + query (x2, mid+1, b );
}
info fr ;
void Init() {
fr = fll(1,N-1,0) ;
memset ( lazy, -1, sizeof lazy ) ;
build ( fr ) ;
q = 0;
visit[0] = 1 ;
}
void TypeLetter(char L) {
++q ;
lst[q] = lst[q-1] ;
update ( fr, q, q, 1 ) ;
let[q] = L ;
}
void UndoCommands(int U) {
++q ;
lst[q] = q ;
nec[q] = U ;
last = q ;
}
char GetLetter(int P) {
while ( !visit[last] ) {
int pos = lst[last] - nec[last] - 1 ;
update ( fr, pos+1, lst[last],0) ;
update ( fr, lst[pos]+1, pos, 1) ;
last = lst [ pos ] ;
}
int lw = 1, hg = q ;
P++ ;
while ( lw < hg ) {
int mid = (lw+hg+1) / 2 ;
int letters = query ( fr, 1, mid ) ;
if ( letters < P ) lw = mid ;
else if ( letters > P ) hg = mid-1 ;
else {
if ( query(fr, mid,mid) ) lw = mid ;
else hg = mid-1 ;
}
}
return let[lw] ;
}
