#include <stdlib.h>
#include <stdio.h>
#define MAXK 1000006
static int K;
static struct STATE{
int len;
char letter;
STATE *prev[20];
} *state[MAXK];
void Init() {}
STATE *make(int len, char letter, STATE *prev)
{
STATE *ret=(STATE*)malloc(sizeof(STATE));
ret->len = len; ret->letter = letter;
for (int i=0;i<20;i++) ret->prev[i] = NULL;
ret->prev[0] = prev;
for (int i=0;i<19&&ret->prev[i];i++){
ret->prev[i+1] = ret->prev[i]->prev[i];
}
return ret;
}
void TypeLetter(char letter)
{
STATE *tmp;
if (state[K]) tmp = make(state[K]->len+1,letter,state[K]);
else tmp = make(1,letter,NULL);
state[++K] = tmp;
}
void UndoCommands(int steps)
{
state[++K] = state[K-steps-1];
}
char GetLetter(int pos)
{
STATE *now=state[K];
int bef=now->len-pos-1,i;
for (i=20;i--;) if ((bef>>i)&1){
now = now->prev[i];
}
return now->letter;
}
