Write a program to convert positive integers into Roman numbers. Assume that the numbers to be converted is less than 5000. The rule for constructing a Roman number is assumed to be as follows. In Roman number system, i is the symbol for 1, v for 5, x for 10, l for 50, c for 100, d for 500 and m for 1000. Symbols with larger values usually appear before symbols with smaller values. The value of a Roman number is, in general, the sum of the values of the symbols. For example, ii is 2, viii is 8. However, if a symbol with smaller value appears before a symbol with larger value, the value of these two symbols is the difference of the two values. For example, iv is 4, ix is 9, and lix is 59. Note that no four consecutive symbols in the Roman number can be the same. For example, iv, but not iiii, is the Roman number 4. The Roman numbers constructed in this way may not be unique. For example, both mcmxc and mxm are valid for 1990. Although the roman number generated by your program need not be the shortest one, never use vv for 10, ll for 100, dd for 1000, or vvv for 15, etc.
The input data is stored in a file. Each record of the input file contains one positive integer x. You may assume that x is less than 5000.
For each number of the input file, print the number in decimal and its Roman form.
The Twentieth Annual International Collegiate Programming Contest