Special State Sort

You are given a list of state names. Your task is to sort the state names in the following way:

• All state names that begin with an uppercase letter should come before those that begin with a lowercase letter.
• Within each group (uppercase and lowercase) the names should be sorted in lexicographical order.

For example, given the input:

5
California texas FLORIDA nevada newYork

The sorted order is:

California
FLORIDA
nevada
newYork
texas

Note: The comparision for lexicographical order is the standard string comparison.

Input and Output

The input is read from stdin and the output should be written to stdout.

inputFormat

The first line contains an integer N which is the number of state names.

The following N tokens represent the state names. They can be separated by spaces or newlines.

outputFormat

Output the sorted state names each on a separate line. First, output all state names that start with an uppercase letter in lexicographical order, followed by those that start with a lowercase letter in lexicographical order.

## sample

5
California texas FLORIDA nevada newYork

California
FLORIDA
nevada
newYork
texas

</p>