#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 info() {
for(int i = 0; i <= last; i++)
cout << node[i].l << ' ';
cout << '\n';
for(int i = 0; i <= last; i++)
cout << node[i].preL[0] << ' ';
cout << '\n';
for(int i = 0; i <= last; i++)
cout << node[i].nbL << ' ';
cout << "\n\n";
}
void TypeLetter(char L) {
int act = node.size();
node.push_back({L, true});
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];
}
node[act].nbL = node[node[act].preL[0]].nbL + 1;
last = act;
//cout << "T\n";
//info();
}
void UndoCommands(int U) {
int act = node.size();
node.push_back({' ', false});
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];
}
node[act].nbL = node[node[act].preL[0]].nbL + 1;
last = act;
//cout << "U\n";
//info();
}
char GetLetter(int P) {
int act = last;
P = node[act].nbL - P - 1;
//cout << "P " << node[act].nbL - P - 1 << ' ' << P << '\n';
//info();
for(int i = T-1; i > -1; i--)
if(P >= (1 << i)) {
act = node[act].preL[i];
P -= 1 << i;
}
return node[act].l;
}
