#include<bits/stdc++.h>
#define mid ((l+r)/2)
#define int long long
#define f(x) x-'a'+1
using namespace std;
int n;
int tot;
int tot_rt;
int root[10000086];
struct sb{
	int ls,rs;
	char data='.';
	int sum;
}a[1000086];
int newNode(){
	return ++tot;
}
int build_tree(int l,int r){
	int node=newNode();
	if(l==r){
		return node;
	}
	a[node].ls=build_tree(l,mid);
	a[node].rs=build_tree(mid+1,r);
	return node;
}
int build_chain(int x,int l,int r,char data){
	int node=newNode();
	a[node].ls=a[x].ls,a[node].rs=a[x].rs;
	a[node].sum=a[x].sum+1;
	if(l==r){
		a[node].data=data;
		return node;
	}
	if(f(data)<=mid){
		a[node].ls=build_chain(a[x].ls,l,mid,data);
	}
	else{
		a[node].rs=build_chain(a[x].rs,mid+1,r,data);
	}
	return node;
}
int getkth(int x,int l,int r,int k){
	if(l==r)return x;
	if(k<=a[a[x].ls].sum)return getkth(a[x].ls,l,mid,k);
	else return getkth(a[x].rs,mid+1,r,k-a[a[x].ls].sum);
}
signed main()
{
	cin>>n;
	root[0]=build_tree(1,n);
	for(int i=1;i<=n;i++){
		char op;
		cin>>op;
		if(op=='T'){
			char x;cin>>x;
			++tot_rt;root[tot_rt]=build_chain(root[tot_rt-1],1,n,x);
		}
		else if(op=='U'){
			int x;cin>>x;
			++tot_rt;root[tot_rt]=root[tot_rt-1-x];
		}
		else{
			int x;cin>>x;
			cout<<a[getkth(root[tot_rt],1,n,x)].data<<"\n";
		}
	}
	return 0;
}