//CrayfishScrivener/IOI2012
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define MAXNLOG 22
#define MAXN 1000500
class Node {
public:
char letter;
Node* parents[MAXNLOG+1];
int level;
Node(Node* parent, char letter = 0) {
level = parent ? parent->level + 1 : 0;
this->letter = letter;
parents[0] = parent;
for (int i = 1; i < MAXNLOG; i++) {
if (parents[i - 1])
parents[i] = parents[i - 1]->parents[i - 1];
else parents[i] = nullptr;
}
}
Node* GetNthParent(int n) {
Node* tar = this;
for (int i = MAXNLOG; i >= 0; i--) {
int p = 1 << i;
if (n & p)tar = tar->parents[i];
if (!tar)return nullptr;
}
return tar;
}
};
Node* NODES[MAXN];
int N = 1;
void Init() {
NODES[0] = nullptr;
}
void TypeLetter(char L) {
NODES[N] = new Node(NODES[N - 1], L);
N++;
}
void UndoCommands(int U) {
NODES[N] = NODES[N - U - 1];
N++;
}
char GetLetter(int L) {
int l = NODES[N - 1]->level;
return NODES[N - 1]->GetNthParent(l-L)->letter;
}
/*
void PrintAll() {
Node* lastNode = NODES[N - 1];
Node* n;
int i = 0;
while (n = lastNode->GetNthParent(i++))
putc(n->letter, stdout);
putc('\n', stdout);
}
*/
