direrctory

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

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
import re
romanNumeralMap = (('M',  1000),
	('CM', 900),
	('D',  500),
	('CD', 400),
	('C',  100),
	('XC', 90),
	('L',  50),
	('XL', 40),
	('X',  10),
	('IX', 9),
	('V',  5),
	('IV', 4),
	('I',  1))
romanNumeralPattern = re.compile("""
    ^                   # beginning of string
    M{0,4}              # thousands - 0 to 4 M's
    (CM|CD|D?C{0,3})    # hundreds - 900 (CM), 400 (CD), 0-300 (0 to 3 C's),
	     #            or 500-800 (D, followed by 0 to 3 C's)
    (XC|XL|L?X{0,3})    # tens - 90 (XC), 40 (XL), 0-30 (0 to 3 X's),
	     #        or 50-80 (L, followed by 0 to 3 X's)
    (IX|IV|V?I{0,3})    # ones - 9 (IX), 4 (IV), 0-3 (0 to 3 I's),
	     #        or 5-8 (V, followed by 0 to 3 I's)
    $                   # end of string
    """ ,re.VERBOSE)

def fromRoman(s):
    """convert Roman numeral to integer"""
    if not s:
        print('Input can not be blank')
        return
    if not romanNumeralPattern.search(s):
        print('Invalid Roman numeral: %s' % s)
        return
    result = 0
    index = 0
    for numeral, integer in romanNumeralMap:
        while s[index:index+len(numeral)] == numeral:
            result += integer
            index += len(numeral)
    return result

def toRoman(n):
    """convert integer to Roman numeral"""
    if not (0 < n < 5000):
        raise OutOfRangeError("number out of range (must be 1..4999)")
    if int(n) != n:
        raise NotIntegerError("decimals can not be converted")

    result = ""
    for numeral, integer in romanNumeralMap:
        while n >= integer:
            result += numeral
            n -= integer
    return result

import collections
import sys

lines = []
while True:
    line = sys.stdin.readline()
    if not line or len(line.strip()) == 0:
        break
    lines.append(line)

names = []
nums  = []
namenum = {}
for line in lines:    
    ins = line.split()
    name = ins[0]
    names.append(name)
    num = fromRoman(ins[1])
    nums.append(num)
for x in range(len(names)):
    if names[x] not in namenum:
        namenum[names[x]] = list()
    namenum[names[x]].append(nums[x])
namenums =  sorted(namenum )
for x in namenums:
    lst = sorted(namenum[x])
    for a in lst:
        print(x + " " + toRoman(a))
    
     
    
    
    
    
  
    


import re
romanNumeralMap = (('M',  1000),
	('CM', 900),
	('D',  500),
	('CD', 400),
	('C',  100),
	('XC', 90),
	('L',  50),
	('XL', 40),
	('X',  10),
	('IX', 9),
	('V',  5),
	('IV', 4),
	('I',  1))
romanNumeralPattern = re.compile("""
    ^                   # beginning of string
    M{0,4}              # thousands - 0 to 4 M's
    (CM|CD|D?C{0,3})    # hundreds - 900 (CM), 400 (CD), 0-300 (0 to 3 C's),
	     #            or 500-800 (D, followed by 0 to 3 C's)
    (XC|XL|L?X{0,3})    # tens - 90 (XC), 40 (XL), 0-30 (0 to 3 X's),
	     #        or 50-80 (L, followed by 0 to 3 X's)
    (IX|IV|V?I{0,3})    # ones - 9 (IX), 4 (IV), 0-3 (0 to 3 I's),
	     #        or 5-8 (V, followed by 0 to 3 I's)
    $                   # end of string
    """ ,re.VERBOSE)

def fromRoman(s):
    """convert Roman numeral to integer"""
    if not s:
        print('Input can not be blank')
        return
    if not romanNumeralPattern.search(s):
        print('Invalid Roman numeral: %s' % s)
        return
    result = 0
    index = 0
    for numeral, integer in romanNumeralMap:
        while s[index:index+len(numeral)] == numeral:
            result += integer
            index += len(numeral)
    return result

def toRoman(n):
    """convert integer to Roman numeral"""
    if not (0 < n < 5000):
        raise OutOfRangeError("number out of range (must be 1..4999)")
    if int(n) != n:
        raise NotIntegerError("decimals can not be converted")

    result = ""
    for numeral, integer in romanNumeralMap:
        while n >= integer:
            result += numeral
            n -= integer
    return result

import collections
import sys

lines = []
while True:
    line = sys.stdin.readline()
    if not line or len(line.strip()) == 0:
        break
    lines.append(line)

names = []
nums  = []
namenum = {}
for line in lines:    
    ins = line.split()
    name = ins[0]
    names.append(name)
    num = fromRoman(ins[1])
    nums.append(num)
for x in range(len(names)):
    if names[x] not in namenum:
        namenum[names[x]] = list()
    namenum[names[x]].append(nums[x])
namenums =  sorted(namenum )
for x in namenums:
    lst = sorted(namenum[x])
    for a in lst:
        print(x + " " + toRoman(a))