#include <bits/stdc++.h>
using namespace std;
//#include "grader.cpp"
const int N=1e6+5;
int curnode, node, len, par[N][30], pos[N], depth[N];
char value[N];
void Init() {}
void TypeLetter(char l) {
len++;
node++;
depth[node]=depth[curnode]+1;
value[node]=l;
par[node][0]=curnode;
pos[len]=node;
curnode=node;
for(int i=1;i<23;i++){
par[node][i]=par[par[node][i-1]][i-1];
}
}
void UndoCommands(int u) {
curnode=pos[len-u];
len++;
pos[len]=curnode;
}
char GetLetter(int p) {
int ans=curnode;
int go=depth[ans]-p-1;
for(int i=0;i<23;i++){
if((go>>i)%2==1)
ans=par[ans][i];
}
return value[ans];
}
/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/
