#python

import sys

def g_c_d (a,b):
    '''Compute the GCD of a and b'''
    while( 1 ):
        a = a % b
        if ( a == 0 ):
	    return b
        b = b % a
        if ( b == 0 ):
            return a
# end GCD

def digit_value(ch):
    '''Give the value of the letter ch in Roman numerals'''
    ch = ch.lower()
    mydict = {'m':1000,'d':500,'c':100,'l':50,'x':10,'v':5,'i':1}
    if ch in mydict:
        return mydict[ch]
    else:
        return 0
# end digit_value

def roman_to_int(roman):
    '''Convert a Roman numeral to an integer'''
    lth = len(roman)
    roman += "Z";
    value = 0
    for i in range(len(roman)-1):
        if (digit_value(roman[i]) < digit_value(roman[i+1])):
            value -= digit_value(roman[i])
        else:
            value += digit_value(roman[i])
    return value
# end roman_to_int

def int_to_roman(mynum):
    '''Convert an integer to a Roman numeral'''
    answer = ""
    symbol = "MDCLXVI"
    numbers = [1000,500,100,50,10,5,1]
    result = [0,0,0,0,0,0,0]
    for i in range(len(numbers)):
        result[i] = mynum / numbers[i]
        mynum = mynum % numbers[i]
    for i in range(len(numbers)):
        if ((i%2==0) and (i != 0) and (result[i]==4)):
            answer += symbol[i]
            answer += symbol[i-1]
        elif ((i%2==1) and (result[i+1]==4) and (result[i]==1)):
            answer += symbol[i+1]
            answer += symbol[i-1]
            result[i]=0
            result[i+1]=0
        else:
            answer += result[i]*symbol[i]
    return answer
# end int_to_roman
    
def number_of_overlaps(s1,s2):
    '''Return the number of overlaps between two strings'''
    if s1 == '':
        return 100
    a = set(s1)
    b = set(s2)
    return len(a & b)
    
def test_percent(i, mynum):
    '''Check to see if mynum is i-th % of some number'''
    if (mynum*100)%i == 0:
        return (mynum*100)/i
    else:
        return 0

def test_frac(mynum, numer, denom):
    '''Check to see if mynum is numer/denom of some number'''
    if (mynum*denom) % numer == 0:
        return (mynum*denom)/numer
    else:
        return 0

def to_multiple(i):
    '''Convert an int into a 'tupled' string'''
    d = ['','','doubled','tripled','quadrupled','quintupled','sextupled','septupled','octupled']
    if i in range(len(d)):
        return d[i]
    else:
        return ''

def print_usage():
    print "Usage: " + sys.argv[0] + " roman_string"
    
def find_percentages(mynum,repeats):
    '''Print all the clues of the form 'x% of y' for the given number'''
    rom = int_to_roman(mynum)
    total = 0
    for i in range(1,1000):
        pct = test_percent(i,mynum)
        if ((number_of_overlaps(int_to_roman(pct),rom) == repeats) and (pct < 4000)):
            print i,
            print "% of " + int_to_roman(pct)
            total += 1
    return total
    
def find_multiples(mynum,repeats):
    '''Print all the clues of the form 'x octupled' (or whatever) for the given number'''
    rom = int_to_roman(mynum)
    total = 0
    for i in range(2,9):
        div1 = mynum/i;
        if (mynum % i == 0) and (number_of_overlaps(int_to_roman(div1),rom) == repeats):
            print int_to_roman(div1) + " " + to_multiple(i)
            total += 1
    return total

def find_multiplication(list,mynum):
    '''Find clues of the form r1 x r2 x r3 x ... ad infinitum (at least 2, of course)'''
    total = 0
    if (reduce(lambda x,y: x*y,list) == mynum):
        # We have a valid product: print it out
        # Note: 1 is always the first element in the list: don't print it
        for i in range(1,len(list)-1):
            print int_to_roman(list[i]) + " x",
        print int_to_roman(list[-1])
        return 1
    else:
        # Go through and recursively try to find products.
        startnum = list[-1]
        startnum = max(2,startnum)
        for j in range(startnum,1+mynum/reduce(lambda x,y: x*y,list)):
            if (number_of_overlaps(int_to_roman(j),int_to_roman(mynum)) == 0) and \
            (mynum % (reduce(lambda x,y: x*y,list)*j) == 0):
                list2 = list[:]
                list2.append(j)
                total += find_multiplication(list2,mynum)
    return total

def find_fractions(mynum,repeats):
    '''Print all the clues of the form 'x/y of z' for the given number'''
    rom = int_to_roman(mynum)
    total = 0
    denominator_list = range(2,21) + range(30,100,10)
    for dem in denominator_list:
        for num in range(1,dem):
            frac=test_frac(mynum,num,dem);
            if (number_of_overlaps(int_to_roman(frac),rom) == repeats \
            and frac < 4000 and frac != mynum and g_c_d(num,dem) == 1 ):
                print num,
                print "/",
                print dem,
                print " of " + int_to_roman(frac)
                total += 1
    return total
 
def ab_cd(mynum): 
    '''Return clues of the form (a+b)*(c+d)
    
    This is a last resort.'''
    ctr = 0;
    rom = int_to_roman(mynum)
    total = 0
    noIs = rom;
    noIs.replace('I','')
    for s1 in range(2,1+mynum/2):
        s2 = mynum - s1;
        for div1 in range(2,1+s1/2):
            div2 = s1/div1;
            if ((s1 % div1 == 0) and (div1<=div2) and \
            number_of_overlaps(int_to_roman(div1),noIs) + \
            number_of_overlaps(int_to_roman(div2),noIs) == 0):
                for d1 in range(2,1+s2/2):
                    d2 = s2/d1;
                    if ( (s2 % d1 == 0) and (d1 <= d2) and \
                    number_of_overlaps(int_to_roman(d1),noIs) +  \
                    number_of_overlaps(int_to_roman(d2),noIs) == 0 and ctr < 20):
                        ctr += 1;
                        print "(" + int_to_roman(div1) + " x " + int_to_roman(div2) + ") + ",
                        print "(" + int_to_roman(d1) + " x " + int_to_roman(d2) + ")"
                        total += 1
    return total
 
def a_multiple(mynum):
    rom = int_to_roman(mynum)
    for div1 in range(2,1+mynum/2):
        if ((mynum % div1 == 0) and (number_of_overlaps(int_to_roman(div1),rom)<=1)):
            print "A multiple of " + int_to_roman(div1)

##################
            
# Check that the script is called correctly
if len(sys.argv) < 2:
    print_usage()
    sys.exit(0)

# Grab the arguments
myroman = sys.argv[1].upper()
mynumber = roman_to_int(myroman)

# Check that the number is a valid Roman numeral
if myroman != int_to_roman(mynumber):
    print "Error: your input is not a valid Roman numeral."
    sys.exit(0)

# Display to the user what he inputted
print myroman + " =",
print mynumber
print # blank line

# To count the number of solutions without repeats
numbernorepeats = 0

# Start to display results without repeats
print "No repeats:"
numbernorepeats += find_percentages(mynumber,0)
numbernorepeats += find_multiplication([1],mynumber)
numbernorepeats += find_multiples(mynumber,0)
numbernorepeats += find_fractions(mynumber,0)

# Do not continue if we already have more than 10 possibilities
if numbernorepeats > 10:
    sys.exit(0)
    
# Otherwise keep going with clues with repeats
numberrepeats = 0
print "\nWith repeats:"
numberrepeats += find_percentages(mynumber,1)
numberrepeats += find_multiples(mynumber,1)
numberrepeats += find_fractions(mynumber,1)

# Last gasp clues.
# Only if we haven't had any clues so far.

if numbernorepeats + numberrepeats > 0:
    sys.exit(0)

numberrepeats += ab_cd(mynumber)

if numberrepeats > 4:
    sys.exit(0)
    
# Our total last gasp: clues like "A multiple of x"
a_multiple(mynumber)