#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) {
cnt++;
memo[cnt] = new Node(L, memo[cnt - 1]);
}
void UndoCommands(int U) {
cnt++;
memo[cnt] = memo[cnt - U - 1];
}
char GetLetter(int P) {
int diff = memo[cnt]->idx - P;
Node *curr = memo[cnt];
for (int i = 0; i < m; i++) {
if (diff & 1) curr = curr->p[i];
}
return curr->c;
}
