202. Integer to Roman

Given an integer num (1 ≤ num ≤ 3999), convert it to a Roman numeral string.

Roman numeral values: I=1, V=5, X=10, L=50, C=100, D=500, M=1000.
Subtractive forms: IV=4, IX=9, XL=40, XC=90, CD=400, CM=900.

Input: A single integer num.

Output: A string — the Roman numeral representation of num.

Examples

Example 1

Input: 3
Output: III
Explanation: 3 = I+I+I.

Example 2

Input: 58
Output: LVIII
Explanation: 58 = 50+5+3 = L+V+III.

Example 3

Input: 1994
Output: MCMXCIV
Explanation: 1994 = 1000+900+90+4 = M+CM+XC+IV.