H. Roman Palindromes
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Given the string $$$S$$$, consisting of letters 'I', 'V', 'X', 'L', 'C', 'D' and 'M'. Your task is to split the string to the minimum number of strings that are:

  • correctly written Roman numerals;
  • palindromes.

The following table from Wikipedia displays how the Roman Numerals are written:

Individual decimal placesThousandsHundredsTensUnits
1MCXI
2MMCCXXII
3MMMCCCXXXIII
4CDXLIV
5DLV
6DCLXVI
7DCCLXXVII
8DCCCLXXXVIII
9CMXCIX
Note that:
  • The numerals for 4, 9, 40, 90, 400 and 900 are written using "subtractive notation" where the first symbol is subtracted from the larger one (for example, for 40 ("XL") 'X' (10) is subtracted from 'L' (50)). These are the only subtractive forms in standard use.
  • A number containing several decimal digits is built by appending the Roman numeral equivalent for each, from highest to lowest.
  • Any missing place (represented by a zero in the place-value equivalent) is omitted.
  • The largest number that can be represented in the Roman notation is 3,999 (MMMCMXCIX).
Input

The first line of the input consists of one integer $$$n$$$ — length of the string ($$$1 \leq n \leq 100\,000$$$).

The second line contains the string of length $$$n$$$, consisting of letters 'I', 'V', 'X', 'L', 'C', 'D' and 'M'.

Output

In first line of the output print one integer $$$k$$$ — the minimum number of correct roman palindromes that can form the given string being concatenated. Then print $$$k$$$ lines, each line containing one string — a correct Roman numeral that is a palindrome, such as the concatenation of all $$$k$$$ lines in the order of output is equal to the given string.

If there is more than one solution, print any of them.

Example
Input
5
MMXXI
Output
3
MM
XX
I