#include <bits/stdc++.h>
using namespace std;
const int k_N = 1e6 + 3;
const int k_Log_N = 20;
int pos[k_N];
int t, cnt;
char c[k_N];
int len[k_N];
int up[k_Log_N][k_N];
void Init() {
t = 0;
for(int i = 0; i < k_Log_N; ++i)
up[i][0] = 0;
pos[0] = 0;
c[0] = '-';
len[0] = 0;
cnt = 1;
}
void TypeLetter(char L){
t++;
pos[t] = cnt;
c[cnt] = L;
len[cnt] = len[pos[t - 1]] + 1;
up[0][cnt] = pos[t - 1];
for(int i = 1; i < k_Log_N; ++i)
up[i][cnt] = up[i - 1][up[i - 1][cnt]];
cnt++;
}
void UndoCommands(int U){
pos[t + 1] = pos[t - U];
t++;
}
char GetLetter(int P){
int go_back = len[pos[t]] - P - 1;
if(!go_back) return c[pos[t]];
int curr = pos[t];
for(int i = k_Log_N - 1; i >= 0; --i)
if(go_back & (1 << i))
curr = up[i][curr];
return c[curr];
}
/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/
