Problem Description

One day, you got tired of the ugly and useless terminal on your computer and decided to implement your own Terminal.

More specifically, it needs to support the following commands:

1. touch filename: If the file named filename does not exist, create such a file. If a file with the same name already exists, do nothing.

2. rm name: Delete the file named name. If such a file does not exist, do nothing.

3. ls: Display all files that currently exist and have not been deleted, in the order of creation time.

4. rename xxx yyy: Rename the file named xxx to yyy. If such a file does not exist, or if a file named yyy already exists, do nothing.

All file names involved consist only of uppercase or lowercase English letters, and file names are case-sensitive.

Input Format

The first line contains an integer $n$, indicating the total number of operations to execute.

The next $n$ lines each contain a string, representing one command.

Output Format

For each ls command, output several lines, each containing one string representing a file name. If there are currently no files, output nothing.

Note that the time limit for this problem is 3 s, and the input/output size is large. Please pay attention to constant factors that affect runtime. We will not provide extra running time for contestants using Java and Python.

6
touch yyh
touch yyhtql
rename yyh yyhnb
touch qwq
rename qwq qaq
ls

yyhnb
yyhtql
qaq

Hint

For $20\%$ of the testdata, only operations $1,3$ exist.

For another $20\%$ of the testdata, only operations $1,2,3$ exist.

For another $20\%$ of the testdata, only operations $1,3,4$ exist.

For $100\%$ of the testdata, $1 \leq n \leq 1000$.

It is guaranteed that the length of every command does not exceed $2000$ characters.

Translated by ChatGPT 5