Stable Case-Insensitive Book Titles Sorting

You are given a list of book titles. Your task is to sort these titles in a case-insensitive manner.

If two titles are equal when compared in a case-insensitive way, you must keep their original order (i.e., the sort must be stable).

Use appropriate stable sorting methods available in your programming language, or implement a stable sort if necessary.

inputFormat

The first line contains an integer n representing the number of book titles. The next n lines each contain one book title (a non-empty string).

outputFormat

Output the sorted list of book titles. Each title should be printed on a new line, sorted in case-insensitive alphabetical order while preserving the relative order for titles which compare equal ignoring case.

## sample

5
Zoo
apple
Apple
book
Book

apple
Apple
book
Book
Zoo

</p>