/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int BITS = 20;
struct Node
{
int length;
char parentLetter;
Node* ancestor[BITS];
Node (char letter = '-')
{
length = 0;
parentLetter = letter;
for(int bit = 0; bit < BITS; bit++)
ancestor[bit] = this;
}
};
Node* root = new Node();
void Init ()
{
;
}
vector <Node*> nodes = {root};
void TypeLetter (char letter)
{
Node* son = new Node(letter);
son->ancestor[0] = nodes.back();
son->length = son->ancestor[0]->length + 1;
for(int bit = 1; bit < BITS; bit++)
{
if(son->ancestor[bit - 1] == root)
son->ancestor[bit] = root;
else
son->ancestor[bit] = son->ancestor[bit - 1]->ancestor[bit - 1];
}
nodes.push_back(son);
}
void UndoCommands (int cnt)
{
nodes.push_back(nodes.end()[- (1 + cnt)]);
}
char GetLetter (int pos)
{
Node* node = nodes.back();
for(int bit = BITS - 1; bit >= 0; bit--)
if(node->length - (1 << bit) > pos)
node = node->ancestor[bit];
return node->parentLetter;
}
