#include <bits/stdc++.h>
using namespace std;
const int T = 20, N = 1 << T;
struct Node {
char l;
bool isLetter;
int nbL, preL[T];
};
int last = 0;
vector<Node> node;
void Init() {
node.push_back({' ', false, 0});
}
void TypeLetter(char L) {
int act = node.size();
node.push_back({L, true, node[last].nbL+1});
if(node[last].isLetter) {
node[act].preL[0] = last;
for(int i = 1; i < T; i++)
node[act].preL[i] = node[node[act].preL[i-1]].preL[i-1];
} else {
for(int i = 0; i < T; i++)
node[act].preL[i] = node[last].preL[i];
}
last = act;
}
void UndoCommands(int U) {
int act = node.size();
node.push_back({' ', false, node[last].nbL});
int pre = act - U - 1;
if(node[pre].isLetter) {
node[act].preL[0] = pre;
for(int i = 1; i < T; i++)
node[act].preL[i] = node[node[act].preL[i-1]].preL[i-1];
} else {
for(int i = 0; i < T; i++)
node[act].preL[i] = node[pre].preL[i];
}
last = act;
}
char GetLetter(int P) {
int act = last;
for(int i = T-1; i > -1; i--)
if(P >= (1 << i)) {
act = node[i].preL[i];
P -= 1 << i;
}
return node[act].l;
}
