#include <bits/stdc++.h>
using namespace std;
const int LOG = 20;
const int N = 1000000;
int p[N], depth[N];
int up[N][LOG];
string word[N][LOG];
int cnt;
void create(int x) {
up[x][0] = p[x];
for (int i = 1; i < LOG; i++) {
up[x][i] = up[up[x][i-1]][i-1];
word[x][i] = word[x][i-1] + word[up[x][i-1]][i-1];
}
}
char getWord(int x, int P) {
int k = depth[x];
string w;
for (int i = LOG - 1; i >= 0; i--) {
if (k & (1 << i)) {
w += word[x][i];
x = up[x][i];
}
}
reverse(w.begin(), w.end());
//cerr << w << '\n';
return w[P];
}
void Init() {
cin.tie(0);
ios::sync_with_stdio(false);
cnt = 0;
}
void TypeLetter(char L) {
if (!cnt) {
p[cnt] = 0;
depth[cnt] = 1;
}
else {
p[cnt] = cnt-1;
depth[cnt] = depth[p[cnt]] + 1;
}
word[cnt][0] += L;
create(cnt);
cnt++;
}
void UndoCommands(int U) {
p[cnt] = cnt - U - 1;
depth[cnt] = depth[p[cnt]]+1;
create(cnt);
cnt++;
}
char GetLetter(int P) {
return getWord(cnt-1, P);
}
