#include<bits/stdc++.h>
using namespace std;
struct character{
int depht;
char letter;
vector<int> Pointers;
};
std::vector<int> Top;
vector<struct character> Tree;
void Init(){
return;
}
int getPointerAtDepht(int start,int depht){
if(Tree[start].depht==depht){
return start;
}
int fix=Tree[start].depht-depht;
int i=-1;
for(;fix>0;i++){
fix/=2;
}
return getPointerAtDepht(Tree[start].Pointers[i],depht);
}
void TypeLetter(char L){
if(Top.size()==0 || Top[Top.size()-1]==-1){
Tree.push_back({0,L,vector<int>()});
}
else{
int prevP=Top[Top.size()-1];
int depht=Tree[prevP].depht+1;
vector<int> Np;
int pos=0;
Np.push_back(prevP);
while(Tree[prevP].Pointers.size()>pos){
prevP=Tree[prevP].Pointers[pos];
Np.push_back(prevP);
pos+=1;
}
Tree.push_back({depht,L,Np});
}
Top.push_back(Tree.size()-1);
}
void UndoCommands(int U){
if(U==Top.size()){
Top.push_back(-1);
}
else{
Top.push_back(Top[Top.size()-1-U]);
}
}
char GetLetter(int P){
int pt=getPointerAtDepht(Top[Top.size()-1],P);
char tmp=Tree[pt].letter;
return Tree[pt].letter;
}
