#include <bits/stdc++.h>
using namespace std;
#define rep(i, j, k) for (int i = j; i < int(k); i++)
constexpr int N = 1e6 + 10;
struct node {
node* par[20];
char c = '\0';
int deep = -1;
node() { fill(par, par + 20, this); }
node(char c_, node* p) {
par[0] = p, c = c_;
deep = p->deep + 1;
rep(i, 1, 20) par[i] = par[i - 1]->par[i - 1];
}
} state[N];
int now;
void Init() { now = 0; }
void TypeLetter(char L) {
now++;
state[now] = node(L, &state[now - 1]);
}
void UndoCommands(int U) {
now++;
state[now] = state[now - U - 1];
}
char GetLetter(int P) {
int goUp = state[now].deep - P;
node* me = &state[now];
rep(i, 0, 20) if (goUp >> i & 1) me = me->par[i];
return me->c;
}
