#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
const int N=1000000;
vector<int> indexs;
int ver=1;
vector<array<int,32>> inf_stack(N);
vector<char> lets(N);
vector<int> lens(N);
void Init() {
lets[0]=' ';
lens[0]=0;
rep(i,32)inf_stack[0][i]=0;
indexs.push_back(0);
}
void TypeLetter(char L) {
lets[ver]=L;
lens[ver]=lens[indexs.back()]+1;
inf_stack[ver][0]=indexs.back();
indexs.push_back(ver);
for(int i=1; i<32; i++){
inf_stack[ver][i]=inf_stack[inf_stack[ver][i-1]][i-1];
}
ver++;
}
void UndoCommands(int U) {
indexs.push_back(indexs[indexs.size()-U-1]);
}
char GetLetter(int P) {
int back=lens[indexs.back()]-P-1;
int pos=indexs.back();
rep(i,32){
if(back&1){
pos=inf_stack[pos][i];
}
back/=2;
}
return lets[pos];
}
