#include<iostream>
#include<vector>
#define MAXN 1000005
using namespace std;
class Tree {
char C[MAXN];
int V=1, d[MAXN], anc[MAXN][20];
public:
int depth(int v) {return(d[v]);}
char get(int v) {return(C[v]);}
int kthanc(int v, int k) {
int res=v;
for (int i=19; i>=0; i--) {
if (k&(1<<i)) {res=anc[res][i];}
}
return(res);
}
int add_node(char c, int par) {
C[V] = c;
d[V] = d[par] + 1;
anc[V][0]=par;
for (int i=1; i<20; i++) {
anc[V][i]=anc[anc[V][i-1]][i-1];
}
return(V++);
}
} T;
vector<int> Pos;
void Init() {
Pos.push_back(0);
}
void TypeLetter(char L) {
Pos.push_back(T.add_node(L, Pos.back()));
}
void UndoCommands(int U) {
Pos.push_back(Pos[Pos.size()-U-1]);
}
char GetLetter(int P) {
return(T.get(T.kthanc(Pos.back(), T.depth(Pos.back())-P-1)));
}
