const int N = 1e6 + 5;
const int LOG = 21;
int cnt,back[N][LOG + 1],sz[N];
char ch[N];
void Init() {
}
void TypeLetter(char L) {
cnt++;
back[cnt][0] = cnt - 1;
for (int i = 1 ; i <= LOG ; i++)
back[cnt][i] = back[back[cnt][i - 1]][i - 1];
sz[cnt] = sz[cnt - 1] + 1;
ch[cnt] = L;
}
void UndoCommands(int U) {
cnt++;
back[cnt][0] = cnt - U - 1;
for (int i = 1 ; i <= LOG ; i++)
back[cnt][i] = back[back[cnt][i - 1]][i - 1];
sz[cnt] = sz[cnt - U - 1];
ch[cnt] = ch[cnt - U - 1];
}
char GetLetter(int P) {
P++;
int x = cnt;
for (int i = LOG ; i >= 0 ; i--)
if (sz[back[x][i]] >= P)
x = back[x][i];
return ch[x];
}
