#include <bits/stdc++.h>
using namespace std;
vector<char> ind2letter; //0th char -- nothing
int curind = 0;
vector<int> depth; //depth of node, length of string
vector<int> seq;
int kthparent[21][1000000];
void Init() {
depth.push_back(0);
ind2letter.push_back('.');
seq.push_back(curind);
for (int i = 0; i<21; i++){
kthparent[i][curind]=-1;
}
curind++;
}
void TypeLetter(char L) {
seq.push_back(curind);
ind2letter.push_back(L);
kthparent[0][curind]=seq[seq.size()-2];
for (int i = 1; i<21; i++){
if (kthparent[i-1][curind]==-1){
kthparent[i][curind]=-1;
} else {
kthparent[i][curind]=kthparent[i-1][kthparent[i-1][curind]];
}
}
depth.push_back(depth[kthparent[0][curind]]+1);
curind++;
}
void UndoCommands(int U) {
seq.push_back(seq[seq.size()-1-U]);
}
int getkthparent(int node, int k){
for (int i = 0; i<21; i++){
if ((1<<i)&k){
node=kthparent[i][node];
}
if (node==-1){
return -1;
}
}
return node;
}
char GetLetter(int P) {
int start = seq[seq.size()-1];
int node = getkthparent(start, depth[start]-P-1);
return ind2letter[node];
}
