#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
int up[N][20], depth[N], pos[N];
char a[N];
int cur=0, timer=0, node=0;
void Init() {
return;
}
void TypeLetter(char L) {
timer++;
node++;
a[node] = L;
up[node][0] = cur;
depth[node] = depth[cur]+1;
cur = node;
pos[timer] = cur;
for(int i=1;i<20;i++){
up[cur][i] = up[up[cur][i-1]][i-1];
}return;
}
void UndoCommands(int U) {
cur = pos[timer-U];
timer++;
pos[timer] = cur;
}
char GetLetter(int P) {
int need = depth[cur]-P-1;
int u=cur;
for(int i=0;i<20;i++){
if((1<<i) & need)u = up[u][i];
}return a[u];
}
