#include<bits/stdc++.h>
using namespace std ;
const int MX = 1e6 + 5 ;
int od = 0 ;
string s = "" ;
struct Node
{
int left = 0 , right = 0 , sum = 0 ;
} emp ;
struct psegtree
{
int cur = 0 , cnt = 0 , N ;
vector<Node> T ;
vector<int> root ;
void init(int n , int m)
{
N = n ;
T = vector<Node> (20*n + 5 , emp) ;
root = vector<int> (m + 5 , 0) ;
}
int _update(int node , int low , int high , int idx , int val)
{
if((idx<low) || (idx>high)) return 0 ;
if((low==high) && (low==idx))
{
++cur ;
T[cur].sum = T[node].sum + val ;
return cur ;
}
int mid = (low+high)>>1 , left = T[node].left , right = T[node].right , par = ++cur ;
if(idx<=mid) T[par].left = _update(left,low,mid,idx,val) , T[par].right = right ;
else T[par].left = left , T[par].right = _update(right,mid+1,high,idx,val) ;
T[par].sum = T[T[par].left].sum + T[T[par].right].sum ;
return par ;
}
void add(int idx)
{
++cnt ;
root[cnt] = _update(root[cnt-1],1,N,idx,1) ;
}
void undo(int x)
{
++cnt ;
root[cnt] = root[cnt-x-1] ;
}
int _query(int node , int low , int high , int idx)
{
if(low==high) return low ;
int mid = (low+high)>>1 , left = T[node].left , right = T[node].right ;
if(T[left].sum>=idx) return _query(left,low,mid,idx) ;
else return _query(right,mid+1,high,idx-T[left].sum) ;
}
int get_val(int idx)
{
return _query(root[cnt],1,N,idx) ;
}
} P ;
void Init()
{
P.init(MX,MX) ;
}
void TypeLetter(char L)
{
s += L ;
P.add(++od) ;
}
void UndoCommands(int U)
{
P.undo(U) ;
}
char GetLetter(int p)
{
return s[P.get_val(p+1)-1] ;
}
