#include <bits/stdc++.h>
using namespace std;
struct node{
int prv;
int sz;
char tp;
int jmp[20];
};
int t=0;
node tab[1000003];
void Init(){
tab[0].sz=-1;
tab[0].prv=0;
for (int i = 0; i<20; i++)tab[0].jmp[i]=0;
}
void TypeLetter(char L){
t++;
tab[t].prv=t-1;
tab[t].sz=tab[t-1].sz+1;
tab[t].tp=L;
tab[t].jmp[0]=t-1;
for (int i = 1; i<20; i++)tab[t].jmp[i]=tab[tab[t].jmp[i-1]].jmp[i-1];
}
void UndoCommands(int U){
t++;
tab[t].prv=tab[t-U-1].prv;
tab[t].sz=tab[t-U-1].sz;
tab[t].tp=tab[t-U-1].tp;
tab[t].jmp[0]=tab[t].prv;
for (int i = 1; i<20; i++)tab[t].jmp[i]=tab[tab[t].jmp[i-1]].jmp[i-1];
}
char GetLetter(int ind){
int cur=t;
for (int i = 19; i>=0; i--)if (tab[tab[cur].jmp[i]].sz>=ind)cur=tab[cur].jmp[i];
return tab[cur].tp;
}
