#include <bits/stdc++.h>
using namespace std;
int anc[1000005][25], ver[1000005], dep[1000005], cur;
char val[1000005];
void Init() {
memset(anc, -1, sizeof anc);
}
void TypeLetter(char L) {
cur++;
val[cur] = L;
ver[cur] = cur;
if (cur > 1) anc[cur][0] = ver[cur - 1], dep[cur] = dep[ver[cur - 1]] + 1;
for (int i = 1; i <= 20; i++)
if (anc[cur][i - 1] != -1)
anc[cur][i] = anc[anc[cur][i - 1]][i - 1];
}
void UndoCommands(int U) {
cur++;
ver[cur] = ver[cur - U - 1];
}
int get_anc(int n, int k) {
int d = dep[n] - k;
for (int i = 0; d > 0; i++, d >>= 1)
if (d & 1) n = anc[n][i];
return val[n];
}
char GetLetter(int P) {
return get_anc(ver[cur], P);
}
