#include <bits/stdc++.h>
using namespace std;
string sth;
int cur = 0;
vector<int> rev;
const int logn = 4;
vector<vector<int>> binj(logn);
vector<int> dep;
int ct = 0;
void Init() {
assert(ct == 0);
sth.push_back(' ');
rev.push_back(-1);
dep.push_back(0);
for (int i = 0; i < logn; i++) {
binj[i].push_back(0);
}
ct++;
}
void TypeLetter(char L) {
rev.push_back(cur);
dep.push_back(dep[cur] + 1);
sth.push_back(L);
binj[0].push_back(cur);
cur = binj[0].size() - 1;
for (int i = 1; i < logn; i++)
binj[i].push_back(binj[i - 1][binj[i - 1][cur]]);
}
void UndoCommands(int U) {
rev.push_back(cur);
cur = rev[rev.size() - U - 1];
}
char GetLetter(int P) {
int jumps = dep[cur] - P - 1;
int tmp = cur;
for (int i = 0; i < logn; i++) {
if ((1 << i) & jumps) {
tmp = binj[i][tmp];
}
}
return sth[tmp];
}
