Lexicographical order is a generalization of the way the alphabetical order of words is based on the alphabetical order of their component letters. An example of lexicographical arrangement is a dictionary or a contact directory.

You are given some names, and your task is to arrange these names in lexicographical order. The interesting part is that some of these names contain roman numerals at end like Louis IV and Henry VII. Take care of these roman numerals as well in correct mathematical order i.e. I<II<III,IV and so on.

INPUT

First line of Input contains a single integer N denoting the number of lines to be followed.

Next N lines contains the names to be arranged. Each line contains a single name.

OUTPUT

N lines, each containing a single name arranged in lexicographical manner.

Constraints

1 ≤ N ≤ 50

Length of a name will be between 1 to 30 characters

No two names will be sameSAMPLE INPUT
4
Henry IX
Louis V
Henry VIII
Charles II

SAMPLE OUTPUT
Charles II
Henry VIII
Henry IX
Louis V

见题面

见题面