const int MAX_CALLS = 1000000 + 5;
const int LOG = 20;
static int up[MAX_CALLS][LOG];
static int versionTail[MAX_CALLS];
static int versionLen[MAX_CALLS];
static char nodeChar[MAX_CALLS];
static int commandCount;
static int nodeCount;
void Init() {
commandCount = 0;
nodeCount = 0;
versionTail[0] = 0;
versionLen[0] = 0;
}
void TypeLetter(char L) {
int currentTail = versionTail[commandCount];
++nodeCount;
nodeChar[nodeCount] = L;
up[nodeCount][0] = currentTail;
for (int j = 1; j < LOG; ++j) {
up[nodeCount][j] = up[up[nodeCount][j - 1]][j - 1];
}
++commandCount;
versionTail[commandCount] = nodeCount;
versionLen[commandCount] = versionLen[commandCount - 1] + 1;
}
void UndoCommands(int U) {
int target = commandCount - U;
++commandCount;
versionTail[commandCount] = versionTail[target];
versionLen[commandCount] = versionLen[target];
}
char GetLetter(int P) {
int node = versionTail[commandCount];
int steps = versionLen[commandCount] - P - 1;
for (int j = 0; j < LOG; ++j) {
if (steps & (1 << j)) {
node = up[node][j];
}
}
return nodeChar[node];
}
