Roman Numeral Rearrangement

Time limit1sMemory limit128 MB

Summary

Given a Roman numeral for a number under 100, rearrange all its characters to form the valid Roman numeral with the smallest possible value.

Level: Medium6 of 10
Topics: Brute force, String, Math, Implementation
Solved: No attempts yet

Problem

The integers from 1 to 9 are written in Roman numerals as I, II, III, IV, V, VI, VII, VIII, and IX.

The multiples of 10 from 10 to 90 are written as X, XX, XXX, XL, L, LX, LXX, LXXX, and XC.

To write a positive integer less than 100 as a Roman numeral, write the tens digit and the ones digit separately using the rules above, then concatenate the two parts.

You are given a Roman numeral B. Rearrange all characters of B, using each character exactly once. Among all valid Roman numerals that can be made this way, output the one with the smallest value.

Input

The first line contains B, the Roman numeral representation of an integer at least 1 and less than 100.

Output

Output the valid Roman numeral with the smallest value that can be made by rearranging the characters of B.

Examples3

Example 1
Input
```
VII
```
Expected output
```
VII
```
Example 2
Input
```
VI
```
Expected output
```
IV
```
Example 3
Input
```
III
```
Expected output
```
III
```