#include <bits/stdc++.h>
using namespace std;
int jump[(int)1e6+2][21];
char ch[(int)1e6+2];
int op = 0;
int dist[(int)1e6+2];
void Init(){
for (int i=0; i<21; i++) jump[0][i] = 0;
dist[0] = 0;
}
void TypeLetter(char L){
op++;
ch[op] = L;
jump[op][0] = op-1;
dist[op] = dist[op-1] + 1;
for (int i=1; i<21; i++){
jump[op][i] = jump[jump[op][i-1]][i-1];
}
}
void UndoCommands(int U){
op++;
ch[op] = ch[op-U-1];
jump[op][0] = jump[op-U-1][0];
dist[op] = dist[op-U-1];
for (int i=1; i<21; i++){
jump[op][i] = jump[jump[op][i-1]][i-1];
}
}
char GetLetter(int P){
int d = dist[op] - P -1;
if (!d) return ch[op];
int s = op;
for (int i=0; i<21; i++){
if (d & (1<<i)) s = jump[s][i];
}
return ch[s];
}
