Alphabetical Aristocrats

Time limit2sMemory limit1024 MB

Summary

Given n surnames, sort them by the substring starting at the first capital letter, using ASCII order, and print the full names.

Level: Easy2 of 10
Topics: String, Sorting
Solved: No attempts yet

Problem

It is the year 1830 of our Lord, 15 years after the Kingdom of the Netherlands gained independence from its French oppressors. You are secretary of state and aide to his highness William I, Grand Duke of Luxembourg and King of the Netherlands, an empire that is destined to prosper and stretch across centuries to come. To the King's utter dismay, rogue scoundrels from the south recently dared to defy his benevolent rule. They call themselves Belgians and declared their own kingdom, a fact that his highness will surely deny for at least another seven to eleven years. King William, in all his wisdom, decided to call upon the most trusted noblemen to scheme a campaign against the insubordinate elements that will last more than nine days.

You are to assemble a list of trustworthy royalty and sort them according to the Dutch rules. The Dutch rules state that surnames are to be compared lexicographically, according to the values of the ASCII characters, and considering only the part starting from the first capital letter. For example, King William compares the surname of his favourite painter Abraham van den Hecken the Younger according to Hecken the Younger.

Input

The input consists of:

One line with an integer $n$ ( $1\leq n\leq 1000$ ), the number of surnames.

$n$ lines, each with a string $s$ ( $1\leq |s|\leq50$ ), one of the surnames. The surnames consist of English letters, spaces, and apostrophes (A-Z, a-z, space, and ').

It is guaranteed that the part starting with the first capital letter is unique. Names have no leading, trailing, or consecutive spaces.

Output

Output the list of surnames, sorted according to the Dutch rules.

Examples3

Example 1

Input

7
van der Steen
fakederSteenOfficial
Groot Koerkamp
Bakker
van den Hecken the Younger
de Waal
van 't Hek

Expected output

Bakker
Groot Koerkamp
van den Hecken the Younger
van 't Hek
van der Steen
fakederSteenOfficial
de Waal

Example 2

Input

5
var Emreis
an Gleanna
Terzieff Godefroy
aep Ceallach
of Rivia

Expected output

aep Ceallach
var Emreis
an Gleanna
of Rivia
Terzieff Godefroy

Example 3

Input

7
van den Brand
den Brand Heek
Brand 'Heek
van Brand heek
DeN bRAnD hEeK
den brandHeek
der Brandheek

Expected output

van den Brand
Brand 'Heek
den Brand Heek
van Brand heek
der Brandheek
DeN bRAnD hEeK
den brandHeek