#include<bits/stdc++.h>
using namespace std;
const int m = 21;
struct Node {
char c;
int idx;
Node *p[m];
Node(char c, Node *par) : c(c) {
if (par) {
idx = par->idx + 1;
p[0] = par;
for (int i = 1; i < m; i++) {
p[i] = p[i - 1]->p[i - 1];
}
} else {
idx = -1;
for (int i = 0; i < m; i++) p[i] = this;
}
}
};
int cnt = 0;
const int N = 1e6 + 5;
Node *memo[N];
void Init() {
memo[0] = new Node('\0', nullptr);
}
void TypeLetter(char L) {
memo[++cnt] = new Node(L, memo[cnt]);
}
void UndoCommands(int U) {
memo[++cnt] = memo[cnt - U];
}
char GetLetter(int P) {
int diff = memo[cnt]->idx - P;
Node *curr = memo[cnt];
for (int i = 0; i < m; i++) {
if (diff & (1 << i)) curr = curr->p[i];
}
return curr->c;
}
