题目描述

大家都知道古罗马人的计数系统。其最严格的定义如下：

1. 用不同的符号（拉丁字母）表示如下数值：

   $$1,\ 5,\ 10,\ 50,\ \ldots,\ 1\cdot 10^i,\ 5\cdot 10^i,\ 1\cdot 10^{i+1},\ 5\cdot 10^{i+1},\ \ldots$$

2. 一个罗马数字写成若干符号组成的序列，这些符号对应的数值之和就是该数的值，除非使用下面的减法规则（第 3、4 条）；

3. 减法规则：一个值为 $1\cdot 10^i$ 的符号可以写在值为 $5\cdot 10^i$ 或 $1\cdot 10^{i+1}$ 的符号前面，此时它在总和中按负数计算；

4. 对于每个 $i$，减法规则最多只能使用一次；

5. 罗马数字中的符号按数值非增顺序排列（应用上述规则时除外）；

6. 罗马数字必须使用最少数量的符号书写。

合法罗马数字示例：I、III、IV、VIII、IX、XVIII、XLII。
非法罗马数字示例：IIII（违反第 6 条）、VX（违反第 3、6 条）、IC（违反第 3 条）、IXIX 和 IIXX（违反第 4 条）、IVX（违反第 3、4 条）、XVIC（违反第 5 条）。

经典罗马数字系统中的符号为：

• I = 1
• V = 5
• X = 10
• L = 50
• C = 100
• D = 500
• M = 1000

该系统中可表示的最大数是：

MMMCMXCIX = 3999

显然，罗马人并不需要处理太大的数字。因此，题目将系统扩展为以下符号：

Q, i, v, x, l, c, d, m, q, a, A, b, B, e, E, f, F, g, G, h, H, j, J, k, K, n, N, o, O, p, P, r, R, s, S, t, T, u, U, w, W, y, Y, z, Z

其中：

• Q = 5000
• i = 10000
• v = 50000
• x = 100000
• 以此类推。

例如，在这个扩展系统中，第 8 个梅森素数 $2^{31}-1$ 可写成：

bbamqdccxlviiiMMMDCXLVII

Alicia 和 Boyan 通过加密信道通信，并且每天更换一次 86.21-bit 的加密密钥。密钥本身会通过不安全信道发送（例如 Viber），为了迷惑窃听者，他们把密钥写成一个扩展罗马数字。此外，消息中还会混入其他字符，而不仅仅是拉丁字母：数字、标点等都可能出现。允许出现所有 ASCII 码在 $33$ 到 $126$ 之间的字符。

窃听者 Eva 记录下了一条长度为 $N$ 的消息。她想从中提取出一个最长的合法扩展罗马数字子序列。这里“子序列”是指字符顺序必须保持不变，但不要求连续。

如果最长的合法扩展罗马数字不唯一，则她希望得到其中数值最大的那个。

请编写程序 roman，输出所求的扩展罗马数字。

输入格式

第一行输入一个正整数 $N$，表示消息长度。
第二行输入该消息本身，共 $N$ 个字符。

保证消息中至少包含一个拉丁字母。

输出格式

输出一个字符串，表示所求的扩展罗马数字。

数据范围

为忠实于原题，本题限制保持原文中的罗马写法：

$$I \le N \le X^V$$

也就是：

$$1 \le N \le 10^5$$

在 $XX\%$ 的数据中：

$$N \le XX$$

也就是在 $20\%$ 的数据中：

$$N \le 20$$

在 $L\%$ 的数据中：

$$N \le M$$

也就是在 $50\%$ 的数据中：

$$N \le 1000$$

样例 1

输入

12
(XVII)<(MCM)

输出

XVII

样例 2

输入

35
2^31-1_=_bbamqdccxxxxviiiMMMDCXLVII

输出

bbamqdccxxxviiiMMMDCXLVII

样例 3

输入

42
MCDLXI_+_LIII_*_MMCXXX_-_MQXCIV_=_xiCCLVII

输出

MMMCMXCVII

样例解释

在第一个样例中，可以从消息中提取出两个合法数字：XVII 和 MCM，其中前者更长，因此答案是 XVII。

如果少一个 I，则正确答案会变成 MCM，因为它更大。
如果 MCM 出现在 XVII 之前，那么答案将会是 MCMXVII。

第二个样例中的大数并不是题面正文里出现的那个数：其中 xl 被替换成了非法的 xxxx（违反第 6 条）。因此在输出中，这一部分只保留了 $3$ 个 x。