#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define fi first
#define se second
using namespace std ;
const int MAXN = 1e6+6 ;
char val[MAXN];
int cnt,t,node,pos[MAXN],len[MAXN],par[MAXN][20];
void Init() {
}
void new_state(int s){
for(int i=1;i<19;i++){
par[s][i] = par[par[s][i-1]][i-1];
}
}
int kth_anc(int u,int k){
for(int i = 18 ; i >= 0 ; i-- ){
if(k&(1<<i)){
k-=(1<<i);
u = par[u][i] ;
}
}
return u;
}
void TypeLetter(char L) {
t ++ ;
pos[t] = cnt ;
par[cnt][0] = node;
len[cnt] = len[node] + 1 ;
node = cnt;
val[cnt] = L ;
new_state(node);
cnt ++ ;
}
void UndoCommands(int U) {
node = pos[t-U];
t++ ;
pos[t] = node ;
}
char GetLetter(int P) {
int L = len[node] ;
// cerr << len[node] << endl;
return val[kth_anc(pos[t],L-P-1)];
}
// int main() {
// Init();
// int cmd_num;
// bool tmp = scanf("%d", &cmd_num);
// assert(tmp == 1);
// int i;
// for (i = 0; i < cmd_num; i++) {
// char cmd;
// tmp = scanf(" %c", &cmd);
// assert(tmp == 1);
// if (cmd == 'T') {
// char letter;
// tmp = scanf(" %c", &letter);
// assert(tmp == 1);
// TypeLetter(letter);
// }
// else if (cmd == 'U') {
// int number;
// tmp = scanf("%d", &number);
// assert(tmp == 1);
// UndoCommands(number);
// }
// else if (cmd == 'P') {
// int index;
// char letter;
// tmp = scanf("%d", &index);
// assert(tmp == 1);
// letter = GetLetter(index);
// printf("%c\n", letter);
// }
// }
// puts("Let's test for cheating!!");
// return 0;
// }
