int cnt,par[22][1000010],num[1000010];
char cs[1000010];
void Init() {
cnt = 1;
num[0] = -1;
}
void TypeLetter(char L) {
cs[cnt] = L;
par[0][cnt] = cnt - 1;
num[cnt] = num[cnt - 1] + 1;
for(int i = 1;i < 22;i++){
if(par[i - 1][cnt]) par[i][cnt] = par[i - 1][par[i - 1][cnt]];
else break;
}
cnt++;
}
void UndoCommands(int U) {
for(int i = 0;i < 22;i++) par[i][cnt] = par[i][cnt - U - 1];
cs[cnt] = cs[cnt - U - 1];
num[cnt] = num[cnt - U - 1];
cnt++;
}
char GetLetter(int P) {
int tmp = cnt - 1;
for(int i = 0;i < 22;i++){
if(num[tmp] == P) break;
if(((num[tmp] - P) >> i) & 1) tmp = par[i][tmp];
}
return cs[tmp];
}
