//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
const int N = 1e6 + 5, LG = 20;
int vertex = 0, cur_vertex = 0, depth[N], lift[N][LG + 5];
char mp[N];
vector<int> command;
void Init() {
mp[0] = '\0', command.push_back(0);
for (int i = 0; i <= LG; i++) lift[0][i] = 0;
}
void TypeLetter(char L) {
vertex++;
int u = cur_vertex, v = vertex;
mp[v] = L;
depth[v] = depth[u] + 1;
lift[v][0] = u;
for (int i = 1; i <= LG; i++) lift[v][i] = lift[lift[v][i - 1]][i - 1];
command.push_back(v);
cur_vertex = v;
}
void UndoCommands(int U) {
int sz = command.size() - 1;
cur_vertex = command[sz - U];
command.push_back(cur_vertex);
}
bool set_bit(int mask, int k) { return mask & (1ll << k); }
char GetLetter(int P) {
int u = cur_vertex, jump = depth[u] - P - 1;
for (int i = 0; i <= LG; i++) {
if (!set_bit(jump, i)) continue;
u = lift[u][i];
}
return mp[u];
}
/*signed main() {
Init();
while (true) {
int type;
cin >> type;
if (type == 1) {
char ch;
cin >> ch;
TypeLetter(ch);
} else if (type == 2) {
int u;
cin >> u;
UndoCommands(u);
} else if (type == 3){
int u;
cin >> u;
cout << GetLetter(u) << endl;
} else break;
}
return 0;
}*/
