#include <bits/stdc++.h>
using namespace std;
const int mxn = 1e6+10;
int par[mxn][20];
int dep[mxn];
int ptr = 0;
string val(mxn,'#');
int now;
vector<int> st;
int newnode(int fa,char c){
ptr++;
dep[ptr] = dep[fa]+1;
val[ptr] = c;
par[ptr][0] = fa;
for(int i = 1;i<20;i++)par[ptr][i] = par[par[ptr][i-1]][i-1];
return ptr;
}
void Init() {
now = 0;
ptr = 0;
st.clear();
dep[0] = 0;
}
void TypeLetter(char L) {
int nxt = newnode(now,L);
now = nxt;
//cerr<<"ADD: "<<L<<endl;
st.push_back(now);
return;
}
void UndoCommands(int U) {
//cerr<<"UNDO: "<<U<<endl;
st.push_back(st.end()[-U-1]);
now = st.back();
//cerr<<"UNDO DONE!"<<endl;
}
char GetLetter(int P) {
int tar = dep[now]-P-1;
int tmp = now;
for(int i = 19;i>=0;i--)if(tar&(1<<i))tmp = par[tmp][i];
//cerr<<"GET: "<<P<<endl;
return val[tmp];
}
