SCRIVENER

#define task "SCRIVENER"

#include <iostream>
#include <cstdio>

using namespace std;

using ll = long long;
using ld = long double;

constexpr int N = 1e6 + 5;
struct node
{
    int dep;
    char v;
    node *child[26], *par[20];
    node()
    {
        dep = 1;
        v = 'a';
        for (int i = 0; i < 26; ++i)
        {
            child[i] = NULL;
            if (i < 20)
                par[i] = NULL;
        }
    }
} root;
node *backup[N], *proot;

int n, m;

void Read()
{
    cin >> n;
}

void Add(char c)
{
    if (!(proot->child[c - 'a']))
        proot->child[c - 'a'] = new node;

    proot->child[c - 'a']->par[0] = proot;
    proot->child[c - 'a']->dep = proot->dep + 1;
    proot = proot->child[c - 'a'];
    proot->v = c;

    for (int i = 1; i < 20; ++i)
        proot->par[i] = (!(proot->par[i - 1])) ? NULL : proot->par[i - 1]->par[i - 1];

    backup[++m] = proot;
}

char Get(int x)
{
    node *a = proot;
    for (int i = 19; ~i; --i)
        if (a->par[i] && a->par[i]->dep >= x)
            a = a->par[i];
    return a->v;
}

void Solve()
{
    m = 1;
    backup[1] = &root;
    proot = &root;

    while (n--)
    {
        char t;
        cin >> t;
        if (t == 'T')
        {
            char c;
            cin >> c;
            Add(c);
        }
        else if (t == 'U')
        {
            int k;
            cin >> k;
            proot = backup[m - k];
            backup[++m] = proot;
        }
        else
        {
            int x;
            cin >> x;
            cout << Get(x + 2) << "\n";
        }
    }
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen(task ".INP", "r"))
    {
        freopen(task ".INP", "r", stdin);
        freopen(task ".OUT", "w", stdout);
    }
    Read();
    Solve();
}