#include <bits/stdc++.h>
using namespace std;
//#define TEST
const int len = 1e6+5, lg = 20;
int dp[len][lg], par[len], dep[len], nod[len], pos;
char val[len];
void Init(){
pos = 0;
for (int i = 0; i < len; i++)
for (int j = 0; j < lg; j++)
dp[i][j] = -1;
}
void TypeLetter(char L){
pos++;
nod[pos] = pos;
par[pos] = nod[pos-1];
val[pos] = L;
dep[pos] = dep[par[pos]]+1;
dp[pos][0] = par[pos];
for (int j = 1; j < lg; j++)
if (dp[pos][j-1] != -1)
dp[pos][j] = dp[dp[pos][j-1]][j-1];
}
void UndoCommands(int U){
pos++;
nod[pos] = nod[pos-U-1];
}
char GetLetter(int P){
int cur = nod[pos];
for (int j = lg-1; j >= 0; j--)
if (dp[cur][j] != -1 && dep[dp[cur][j]] > P)
cur = dp[cur][j];
return val[cur];
}
#ifdef TEST
int main() {
freopen("example.txt", "r", stdin);
Init();
int cmd_num;
int 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;
}
#endif // TEST
