//#include "scrivener.h"
#include <bits/stdc++.h>
using namespace std;
#define sz size()
#define pb push_back
const int MAXM = 1e6 + 5;
const int LOG = 20;
#define ff first
#define ss second
#define ll long long
string s;
vector <int> v;
int tr, idx, pr, P[MAXM][LOG], lvl[MAXM];
char val[MAXM];
void Init() {
return;
}
void TypeLetter(char L) {
idx++;
val[idx] = L;
P[idx][0] = pr;
lvl[idx] = lvl[pr] + 1;
v.pb (idx);
pr = idx;
for (int j = 1; j < LOG; ++j) {
if (P[idx][j - 1]) {
P[idx][j] = P[P[idx][j - 1]][j - 1];
}
}
}
void UndoCommands(int U) {
pr = v[(int)v.sz - U - 1];
v.pb (pr);
}
char GetLetter(int PP) {
int san = lvl[pr] - (PP + 1);
int jog = pr;
for (int i = LOG - 1; i >= 0; i--) {
if (san>>i&1) {
jog = P[jog][i];
}
}
return val[jog];
}
//#include <stdlib.h>
//#include <stdio.h>
//#include <assert.h>
//
//#define inbuf_len 1 << 16
//#define outbuf_len 1 << 16
//
//
//int main() {
//// Typeletter ('a');
//// return 0;
// freopen ("input.txt", "r", stdin);
// int tmp;
//
// /* Set input and output buffering */
// char *inbuf, *outbuf;
// inbuf = (char*) malloc(inbuf_len * sizeof(char));
// outbuf = (char*) malloc(outbuf_len * sizeof(char));
// tmp = setvbuf(stdin, inbuf, _IOFBF, inbuf_len);
// tmp = setvbuf(stdout, outbuf, _IOFBF, outbuf_len);
//
// Init();
//
// int cmd_num;
// 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", letter);
// }
// }
//
// printf("\n");
// return 0;
//
//}
