Integer to Roman

Hartfield Museum has the reverse problem when it commissions a new plaque: the catalogue holds an ordinary year and the engraver needs the Roman numeral to cut. The symbols are I = 1, V = 5, X = 10, L = 50, C = 100, D = 500 and M = 1000, written largest first. But a smaller symbol placed immediately before a larger one counts downward rather than upward, and it is that shorter form the engraver expects: 4 is cut as IV and never as IIII, and 900 is CM and never DCCCC.

Task: Print the Roman numeral for n, in the standard shortest form.

Input

A single line holding one integer n, with 1 <= n <= 3999.

Output

One line holding the numeral in upper case, with no spaces and nothing else.

Example:

Input:
1994

Output:
MCMXCIV