#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAX_N 1000000
#define MAX_LN 20
vector<char> c;
int idx[MAX_N+1];
int fr[MAX_N+1][MAX_LN+1];
int ln[MAX_N+1];
int index=0;
int t = 0;
void Init(){
c.clear();
ln[0] = -1;
index = t = 0;
}
void TypeLetter(char L) {
//cout<<index<<endl;
fr[c.size()][0] = index;
ln[c.size()] = ln[index]+1;
index = c.size();
c.push_back(L);
for(int i=1; i<=MAX_LN; i++){
fr[index][i] = fr[fr[index][i-1]][i-1];
}
idx[t++] = index;
}
void UndoCommands(int U) {
//cout<<index<<endl;
index = idx[t-U-1];
idx[t++] = index;
}
char GetLetter(int P) {
//cout<<index<<endl;
int now = index;
P = ln[now] - P;
int k = (1<<20);
for(int i=20; i>=0; i--){
if(k<=P){
P-=k;
now = fr[now][i];
}
k = (k>>1);
}
//cout<<"*"<<now<<endl;
return c[now];
}
