// - Art -
#pragma GCC optimize("O3,unroll-loops") // O2
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define el cout << '\n'
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c) for (int i = 0, _c = (c); i < _c; ++i)
const int N = 1e6 + 7;
using namespace std;
char ans[N];
int sz, depth[N], par[N][20];
void Init() {
par[0][0] = 0;
}
void TypeLetter(char L) {
ans[++sz] = L;
par[sz][0] = sz - 1;
depth[sz] = depth[sz - 1] + 1;
// FOR (j, 1, 19) {
for (short j = 1; j <= 19; ++j) {
par[sz][j] = par[par[sz][j - 1]][j - 1];
}
}
void UndoCommands(int U) {
ans[++sz] = 'X';
par[sz][0] = sz - U - 1;
depth[sz] = depth[sz - U - 1];
// FOR (j, 1, 19) {
for (short j = 1; j <= 19; ++j) {
par[sz][j] = par[par[sz][j - 1]][j - 1];
}
}
char GetLetter(int P) {
++P; // 1-based idx
int u = sz;
// REV (i, 19, 0) {
for (short i = 19; i >= 0; --i) {
if (depth[par[u][i]] >= P) {
u = par[u][i];
}
}
return ans[u];
}
// int main() {
// #define name "scrivener"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
// ios_base::sync_with_stdio(false);
// cin.tie(0); cout.tie(0);
// int subtask;
// cin >> subtask;
// int q;
// cin >> q;
// while (q--) {
// char tp;
// cin >> tp;
// if (tp == 'T') {
// char c;
// cin >> c;
// TypeLetter(c);
// }
// else if (tp == 'U') {
// int k;
// cin >> k;
// UndoCommands(k);
// }
// else {
// int i;
// cin >> i;
// cout << GetLetter(i);
// }
// }
// return 0;
// }
