#include<bits/stdc++.h>
using namespace std;
#define ll long long
char last;
struct CMD{
vector<int> prev;
int depth;
char added;
int rep;
CMD(){
prev.resize(20, 0);
added = ' ';
depth = 0;
rep = 0;
}
};
vector<CMD> tree;
void add_to_tree(int _prev, char _added){
CMD r;
r.prev[0] = _prev;
r.added = _added;
r.depth = tree[_prev].depth +1;
r.rep = tree.size();
for(int i = 1; i<20; i++){
r.prev[i] = tree[r.prev[i-1]].prev[i-1];
}
tree.push_back(r);
}
string s;
void Init() {
tree.push_back(CMD());
}
void TypeLetter(char L) {
last = L;
add_to_tree(tree.back().rep, last);
}
void UndoCommands(int U) {
tree.push_back(CMD());
tree.back().rep = tree[tree.size()-2-U].rep;
}
char get_anc(int id, int dist){
int cur = id;
for(int i = 19; i>=0; i--){
if((dist & (1<<i))!=0){
cur = tree[cur].prev[i];
}
}
return tree[cur].added;
}
char GetLetter(int P) {
return get_anc(tree.back().rep, tree[tree.back().rep].depth-P-1);
}
