#include <bits/stdc++.h>
using namespace std;
const int mxN = 1e6+5;
vector<int> de(mxN), po(mxN);
vector<vector<int>> up(mxN,vector<int>(20));
vector<char> ou(mxN);
int cu1 = 0, cu2 = 0, cu3 = 0;
void Init() {}
void TypeLetter(char L) {
cu1++;
cu2++;
ou[cu2] = L;
up[cu2][0] = cu3;
de[cu2] = de[cu3]+1;
cu3 = cu2;
po[cu1] = cu3;
for(int i = 1; i < 20; ++i){
up[cu3][i] = up[up[cu3][i-1]][i-1];
}
}
void UndoCommands(int U) {
cu3 = po[cu1-U];
po[++cu1] = cu3;
}
char GetLetter(int P) {
int get = de[cu3]-P-1;
int ind = cu3;
for(int i = 0; i < 20; ++i){
if((1<<i)&get)ind = up[ind][i];
}return ou[ind];
}
