Sorting Words with Single Character Modification

You are given a list of n words. You are allowed to change exactly one character in one word to any other alphabetic character (from \(a\) to \(z\)) at most once before sorting the entire list in alphabetical order.

Your task is to choose whether to perform a single-character modification or not, so that after sorting the list the result is the lexicographically smallest possible. In other words, let \(L\) be the sorted list of the original words. You may choose a candidate modification in one word (by changing one character) and then sort the resulting list. Compare the sorted list (treated as a tuple of strings) with \(L\) in lexicographical order. If a modification yields a smaller sorted list, you must output that; otherwise, output the original sorted list.

Note: In the sample test cases, it turns out that applying a modification does not lead to a lexicographically smaller sorted list, so the output is simply the original list sorted in alphabetical order.

Example:

Input:
5
cat
dog
banana
apple
zebra
Output:
apple banana cat dog zebra

</p>

inputFormat

The input is given via standard input and consists of:

• The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the number of words.
• Each of the next \(n\) lines contains a single word made up of lowercase alphabetic characters.

outputFormat

Output the sorted list of words in one line, separated by spaces. The list should be the lexicographically smallest one achievable by optionally applying a single-character modification as described.

## sample

5
cat
dog
banana
apple
zebra

apple banana cat dog zebra

</p>