rt

#include <bits/stdc++.h>
using namespace std;
#define mi int mid = (l+r)>>1;
#define GO(__start,__end,__var) for(int __var = __start ; __var<=__end ; __var++)
#define GON(__start,__end,__var,_comp,_ope,_type) for(_type __var = __start ; __var _comp __end ; __var _ope)
#define GOGRA(__edge,__head,__start,__var) for(int __var = __head[__start];__var;__var=__edge[__var].next)
#define COMP(__type,__member,__comp) [=](__type a1,__type a2)->bool{ return a1.__member __comp a2.__member;}
const int maxn=1e6+12,maxm=3000;
typedef long long lld;
typedef double lf;
namespace io{
    inline int fr(){
        register int x=0,dis=1;
        register char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch =='-')dis=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=(x<<1)+(x<<3)+(ch^48);
            ch = getchar();
        }
        return x*dis;
    }
    inline lld fr_lld(){
        lld x=0,dis=1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-')dis=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=(x<<1)+(x<<3)+(ch^48);
            ch = getchar();
        }
        return x*dis;
    }
    inline lf fr_lf(){
        lf x=0;int dis =1;lf l=0.1;
        char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-')dis=-1;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x= 10*x+(ch^48);
            ch=getchar();
        }
        if(ch=='.'){
            ch=getchar();
            while(ch>='0'&&ch<='9'){
                x = x+l*(ch^48);
                l*=0.1;
            }
        }
        return x*dis;
    }
    inline void fw(int num){
        if(num<0){
            putchar('-');
            num=-num;
        }
        if(num>9)fw(num/10);
        putchar(num%10+'0');
    }
    inline void fw_lld(lld num){
        if(num<0){
            putchar('-');
            num=-num;
        }
        if(num>9)fw_lld(num/10);
        putchar(num%10+'0');
    }
}
using namespace io;
int t[maxn<<1],lson[maxn<<1],rson[maxn<<1];
int cnt,root[maxn],version;
int len[maxn],le;
inline void clone(int &k){
    t[++cnt]=t[k];
    lson[cnt]=lson[k];
    rson[cnt]=rson[k];
    k=cnt;
}
inline void update(int &k,int l,int r,char x){
    clone(k);
    if(l==r){
        t[k]=x;
        return;
    }
    mi;
    if(le<=mid)update(lson[k],l,mid,x);
    else update(rson[k],mid+1,r,x);
    return;
}
inline char query(int k,int l,int r,int v){
    if(!k)return 0;
    if(l==r)return t[k];
    mi;
    return v<=mid?query(lson[k],l,mid,v):query(rson[k],mid+1,r,v);
}
int n;
inline void Read(){
    n=fr();
    return;
}
inline void Solve(){
    GO(1,n,i){
        char op;
        cin>>op;
        if(op=='T'){
            char x;
            cin>>x;
            le++;
            int temp=root[version];
            update(temp,1,n,x);
            root[++version]=temp;len[version]=le;
        }
        else if(op=='Q'){
            int x;
            cin>>x;
            cout<<query(root[version],1,n,x)<<endl;
        }
        else if(op=='U'){
            int x;
            cin>>x;
            le=len[version-x];
            root[++version]=root[version-x-1];
        }
    }
    return;
}
int main(){
    // freopen("Chorse.in","r",stdin);
    // freopen("Chores.out","w",stdout);
    Read();
    Solve();
    return 0;
}