#include <vector>
using namespace std;
struct node {
char letter;
int ancestors[20];
int depth;
};
node history[1000001];
int moves = 0;
void Init() {
history[0].depth = 0;
for (int i=0; i<1000001; i++) {
for (int j=0; j<20; j++) history[i].ancestors[j] = -1;
}
}
void TypeLetter(char L) {
moves++;
history[moves].letter = L;
history[moves].depth = history[moves-1].depth+1;
history[moves].ancestors[0] = moves-1;
for (int i=1; i<20; i++) {
if (history[history[moves].ancestors[i-1]].ancestors[i-1] == -1) break;
history[moves].ancestors[i] = history[history[moves].ancestors[i-1]].ancestors[i-1];
}
}
void UndoCommands(int U) {
moves++;
history[moves] = history[moves-U-1];
}
char GetLetter(int P) {
node ans = history[moves];
for (int i=0; i<20; i++) {
if ((history[moves].depth-P-1)&(1<<i)) ans = history[ans.ancestors[i]];
}
return ans.letter;
}
