Integer to Roman

Medium · strings

Roman numerals write a number with these seven letters:

| Letter | I | V | X | L | C | D | M | |---|---|---|---|---|---|---|---| | Value | 1 | 5 | 10 | 50 | 100 | 500 | 1000 |

A number is written one decimal digit at a time, from the thousands down to the units. Each digit uses the letters for its own place: a "one" letter, a "five" letter and a "ten" letter (for the units these are I, V, X, for the tens X, L, C, for the hundreds C, D, M, and for the thousands only M is used). A digit d of that place is written like this:

0 is not written at all.
1, 2 and 3 are the "one" letter repeated d times.
4 is the "one" letter followed by the "five" letter.
5 is the "five" letter.
6, 7 and 8 are the "five" letter followed by the "one" letter repeated d - 5 times.
9 is the "one" letter followed by the "ten" letter.

The digit blocks are then written one after another, thousands first. For example, 49 is XLIX: the tens digit 4 gives XL and the units digit 9 gives IX.

Given a whole number num, return its Roman numeral as a string.

Examples

Example 1

Input: num = 14

Output: "XIV"

The tens digit 1 gives X and the units digit 4 gives IV.

Example 2

Input: num = 1987

Output: "MCMLXXXVII"

Thousands 1 gives M, hundreds 9 gives CM, tens 8 gives LXXX and units 7 gives VII.

Example 3

Input: num = 3999

Output: "MMMCMXCIX"

The largest allowed number: MMM, then CM, XC and IX.

Constraints

1 <= num <= 3999