Integer to Roman Numeral Conversion

You are given an integer n (1 ≤ n ≤ 3999). Your task is to convert this integer into its Roman numeral representation.

Roman numerals are represented by combinations of letters from the Latin alphabet: I, V, X, L, C, D, M. Numerals are generally written from largest to smallest and the numeral system follows these rules:

• The symbols I, X, C, M can be repeated up to three times in succession.
• The symbols V, L, D are never repeated.
• Subtractive Notation: A smaller numeral placed before a larger numeral indicates subtraction. For instance, $I\,V = IV$ (4) and $I\,X = IX$ (9). Other subtractive pairs include: $X\,L = XL$ (40), $X\,C = XC$ (90), $C\,D = CD$ (400), and $C\,M = CM$ (900).

The formula for the conversion essentially subtracts the largest possible Roman numeral values from the given number until it reaches 0.

inputFormat

The input is given via standard input and consists of a single line containing one integer n (1 ≤ n ≤ 3999).

outputFormat

Output the Roman numeral representation of the given number to standard output.

## sample

1

I

</p>