#include<bits/stdc++.h>
using namespace std;
#define INIT ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount
int tmp=0;
struct nod{
nod *l, *r;
char c;
int ln;
nod(nod *l, nod *r){
this->l=l;
this->r=r;
this->ln=l->ln+r->ln;
}
nod(char c){
if(c=='-'){
this->c=c;
this->ln=0;
this->r=NULL;
this->l=NULL;
return;
}
this->ln=1;
this->l=NULL;
this->r=NULL;
this->c=c;
}
} *ver[1000010];
nod *add(nod *v, int l, int r, char c){
if(l==r){
return new nod(c);
}
int mid=(l+r)>>1ll;
if( (v->l->ln)==(mid-l+1) ){
return new nod(v->l, add(v->r, mid+1, r, c) );
}
else{
return new nod(add(v->l, l, mid, c), v->r );
}
}
char get_char(nod *v, int l, int r, int p){
if(l==r){
return v->c;
}
int mid=(l+r)>>1ll;
if(p<=mid){
return get_char(v->l, l, mid, p);
}
else{
return get_char(v->r, mid+1, r, p);
}
}
nod *build(int l, int r){
if(l==r){
return new nod('-');
}
int mid=(l+r)>>1ll;
return new nod(build(l, mid), build(mid+1, r) );
}
void Init() {
ver[0]=build(1, 1000000);
}
void TypeLetter(char L) {
ver[tmp+1]=add(ver[tmp], 1, 1000000, L);
tmp++;
}
void UndoCommands(int U){
ver[tmp+1]=ver[tmp-U];
tmp++;
}
char GetLetter(int P){
return get_char(ver[tmp], 1, 1000000, P+1);
}
