#include <bits/stdc++.h>
using namespace std;
struct node{
	string name;
	int num;
}s[1010];
string x;
string nm;
string last,now;
inline int cmp(const node &a,const node &b){
	return a.num<b.num;
}
inline int find_a(string a,int k){
	if (k==0)
		return 0;
	for(int i=1;i<=k;i++)
		if (s[i].name==a)
			return i;
	return 0;
}
inline void rename(string a,string b,int k){
	if (k==0)
		return;
	if (find_a(a,k)==0)
		return;
	s[find_a(a,k)].name=b;
	return;
}
inline void rm(string a,int k){
	if (k==0)
		return;
	if (find_a(a,k)==0)
		return;
	s[find_a(a,k)].name="\0";
	return;
}
inline void ls(int k){
	if (k==0)
		return;
	sort(s+1,s+1+k,cmp);
	for(int i=1;i<=k;i++)
		if (s[i].name!="\0")
			cout<<s[i].name<<endl;	
	return;
}
signed main(){
	int n,cnt=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		cin>>x;
		if (x=="touch")
			cin>>s[++cnt].name;
		if (x=="rm")
			cin>>nm,rm(nm,cnt);
		if (x=="ls")
			ls(cnt);
		if (x=="rename")
			cin>>last>>now,rename(last,now,cnt);
	}
	return 0;
}
=