#include <vector>
#include <string>
#include <stdio.h>
using namespace std;
vector<vector<int>> Log;
int nd; //nodo attuale
vector<char> C;
vector<int> P;
vector<int> D;
void Ancestors()
{
Log.push_back(vector<int>(25,0));
Log[nd][0] = P[nd];
for(int i=1; i<25; i++)
{
Log[nd][i] = Log[Log[nd][i-1]][i-1];
}
}
void Init()
{
//crea radice
C.push_back(' ');
P.push_back(-1);
D.push_back(-1);
Log.push_back(vector<int>(25,0));
nd = 0;
}
void UndoCommands(int U)
{
C.push_back(C[nd-U]);
P.push_back(P[nd-U]);
D.push_back(D[nd-U]);
Log.push_back(Log[nd-U]);
nd ++;
}
void TypeLetter(char ch)
{
C.push_back(ch);
P.push_back(nd);
D.push_back(D[nd]+1);
nd ++;
Ancestors();
}
char GetLetter(int i)
{
i = D[nd] - i;
int ndattuale = nd;
for(int e=0; e<25; e++)
{
if((1<<e) & i)//potenza di 2 contenuta
{
ndattuale = Log[ndattuale][e];
}
}
return C[ndattuale];
}
