给你一个由 ASCII 码在 34 到 126 之间（包含边界）的字符组成的字符串。该字符串中的大写和小写字母 I, i, V, v, X, x, L, l, C, c, D, d, M, m 被视为罗马数字；小写和大写字母被视为相同。你的任务是从这些字符中拼凑出罗马数字系统中最长的可能数字（给定的字母可以任意重新排列）。如果存在多个这样的数字，选择其中数值最大的一个。

罗马数字系统的规则如下。上述字母 I, V, X, L, C, D 和 M（罗马数字）分别对应数值 1, 5, 10, 50, 100, 500 和 1000。罗马数字系统中的数字不能有超过三个连续的相同字母。字符 V, L, D 中的每一个最多只能出现一次。字母 I, X 和 C 可以分别放在字母 X, C 和 M 之前以组成 9, 90 和 900，或者放在字母 V, L 和 D 之前以组成 4, 40 和 400。

IX 和 IV 后面不能跟任何其他字符，XL 和 XC 后面只能跟 V 或 I，CD 和 CM 后面只能跟 L, X, V 或 I。例如，IVII 不是一个正确的罗马数字。

在其他情况下，一个数字放在另一个数字后面仅表示这些数字的和。

最后，较小的数字必须放在较大或相同的数字后面（这里组合 IV, XC, ... 被视为像单个数字一样）。因此，罗马数字系统中的数字表示是唯一的。

输入格式

输入文件的第一行包含一个非空字符串，由 ASCII 码在 34 到 126 之间（包含边界）的字符组成。字符串长度不超过 100 000 个字符。

输出格式

请输出由给定字符串中的字符能组成的所有罗马数字中，长度最长且数值最大的那个。所有罗马数字均用大写字母表示。

样例

输入样例 1

Xiva

输出样例 1

XVI

输入样例 2

zErO

输出样例 2

输入样例 3

ixvIii

输出样例 3

XVIII