#include<bits/stdc++.h>
using namespace std;
const int lim = 1e6 + 5;
pair<int, int>up[lim][21];
vector<char>S;
void Init(){
for(int i = 0; i < lim; i++){
for(int j = 0; j < 21; j++){
up[i][j] = make_pair(0, 0);
}
}
S.emplace_back('#');
}
void add_edge(int u, int v, bool w){
up[u][0] = make_pair(v, int(w));
for(int i = 1; i < 21; i++){
up[u][i].first = up[up[u][i - 1].first][i - 1].first;
up[u][i].second = up[u][i - 1].second + up[up[u][i - 1].first][i - 1].second;
}
}
void TypeLetter(char L){
add_edge(S.size(), int(S.size()) - 1, true);
S.emplace_back(L);
}
void UndoCommands(int U){
add_edge(S.size(), int(S.size()) - U - 1, false);
S.emplace_back('#');
}
char GetLetter(int P){
add_edge(S.size(), int(S.size()) - 1, false);
P = up[S.size()][20].first - P - 1;
int index = S.size();
S.emplace_back('#');
for(int i = 20; i > -1; i--){
if(up[index][i].second <= P){
P -= up[index][i].second;
index = up[index][i].first;
}
}
return S[index];
}
