#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int MAX = 1e6 + 5;
int moves = 1;
vi rt(MAX); // prev time if reverting
vi len(MAX); // depth of vertex
char ch[MAX]; // character at vertex
int par[MAX]; // parent
int binjump[MAX][25];
void Init() {
for (int i = 0; i < MAX; i++) {
rt[i] = i;
}
}
void addEdge(int n, int p, char L) { // edge from p to n, L at n
par[n] = p;
// do the binjump
binjump[n][0] = p;
for (int i = 1; i < 25; i++) {
binjump[n][i] = binjump[binjump[n][i - 1]][i - 1];
}
}
void TypeLetter(char L) {
len[moves] = len[moves - 1] + 1;
ch[moves] = L;
addEdge(moves, rt[moves - 1], L);
moves++;
}
void UndoCommands(int U) {
rt[moves] = rt[moves - U - 1];
len[moves] = len[moves - U - 1];
moves++;
}
char anc(int n, int m) { // char stored at m nodes above n
int curr = n;
for (int i = 0; i < 25; i++) {
if (m & (1 << i))
curr = binjump[curr][i];
}
return ch[curr];
}
char GetLetter(int P) {
int mv = len[rt[moves - 1]] - P - 1;
// cout<<"mv: "<<mv<<endl;
return anc(rt[moves - 1], mv);
}
