Integer to Roman

Roman numerals use seven letters, each with a fixed value:

I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000.

Given a whole number num, return its standard Roman numeral. To build it, write the decimal digits of num one at a time, from the thousands down to the units, and join the pieces. Each digit uses only the letters for its own place: a one, a five and a ten of that place.

• units: one I, five V, ten X;
• tens: one X, five L, ten C;
• hundreds: one C, five D, ten M;
• thousands: one M (the thousands digit is at most 3, so it is just M, MM or MMM).

A digit d is written with its place's letters like this (shown with the units' letters):

• 1, 2, 3: the one letter, repeated d times (I, II, III);
• 4: one before five (IV), meaning five minus one;
• 5: five alone (V);
• 6, 7, 8: five followed by d - 5 ones (VI, VII, VIII);
• 9: one before ten (IX), meaning ten minus one;
• 0: nothing at all.

So a letter is never repeated more than three times in a row, and the only pairs with a smaller letter in front are IV, IX, XL, XC, CD and CM. Shortcuts across places, like IL for 49 or IM for 999, are not allowed.

Constraints

• 1 <= num <= 3999