CF61C.Capture Valerian

It's now 260 AD. Shapur, being extremely smart, became the King of Persia. He is now called Shapur, His majesty King of kings of Iran and Aniran.

Recently the Romans declared war on Persia. They dreamed to occupy Armenia. In the recent war, the Romans were badly defeated. Now their senior army general, Philip is captured by Shapur and Shapur is now going to capture Valerian, the Roman emperor.

Being defeated, the cowardly Valerian hid in a room at the top of one of his castles. To capture him, Shapur has to open many doors. Fortunately Valerian was too scared to make impenetrable locks for the doors.

Each door has 4 parts. The first part is an integer number a. The second part is either an integer number b or some really odd sign which looks like R. The third one is an integer c and the fourth part is empty! As if it was laid for writing something. Being extremely gifted, after opening the first few doors, Shapur found out the secret behind the locks.

c is an integer written in base a, to open the door we should write it in base b. The only bad news is that this R is some sort of special numbering system that is used only in Roman empire, so opening the doors is not just a piece of cake!

Here's an explanation of this really weird number system that even doesn't have zero:

Roman numerals are based on seven symbols: a stroke (identified with the letter I) for a unit, a chevron (identified with the letter V) for a five, a cross-stroke (identified with the letter X) for a ten, a C (identified as an abbreviation of Centum) for a hundred, etc.:

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

Symbols are iterated to produce multiples of the decimal (1, 10, 100, 1, 000) values, with V, L, D substituted for a multiple of five, and the iteration continuing: I 1, II 2, III 3, V 5, VI 6, VII 7, etc., and the same for other bases: X 10, XX 20, XXX 30, L 50, LXXX 80; CC 200, DCC 700, etc. At the fourth and ninth iteration, a subtractive principle must be employed, with the base placed before the higher base: IV 4, IX 9, XL 40, XC 90, CD 400, CM 900.

Also in bases greater than 10 we use A for 10, B for 11, etc.

Help Shapur capture Valerian and bring peace back to Persia, especially Armenia.

现在是公元260年。聪明绝顶的沙普尔（Shapur）成为了波斯国王，尊号为“伊朗与阿尼兰诸王之王”。

近日，罗马人向波斯宣战，妄图侵占亚美尼亚。在最近的战争中，罗马军队惨遭失败。如今，罗马高级将领菲利普（Philip）已被沙普尔俘获，而沙普尔正准备俘获罗马皇帝瓦莱里安（Valerian）。

战败之后，胆小如鼠的瓦莱里安躲进了他某座城堡顶层的一间密室中。为了抓住他，沙普尔必须打开许多扇门。幸运的是，极度恐惧的瓦莱里安并未给这些门安装坚不可摧的锁。

每扇门由四部分组成：第一部分是一个整数 $a$；第二部分要么是一个整数 $b$，要么是一个极为怪异的符号——看起来像字母 R；第三部分是一个整数 $c$；第四部分则为空白！仿佛专为书写内容而预留。凭借过人的天赋，在打开前几扇门后，沙普尔便破解了这些锁的秘密：

$c$ 是以 $a$ 进制表示的一个整数；要打开这扇门，我们必须将它转换为 $b$ 进制表示。唯一不利的消息是：这个 R 代表一种仅在罗马帝国使用的特殊记数系统，因此开门绝非易事！

下面是对这种极其怪异、甚至没有“零”的记数系统的解释：

罗马数字基于七个符号：竖线（用字母 I 表示）代表一单位，倒 V 形（用字母 V 表示）代表五，十字形（用字母 X 表示）代表十，C（源自拉丁语 Centum，意为“百”）代表一百，等等：

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

通过重复符号来表示十进制（1、10、100、1 000）各基数的倍数，其中 V、L、D 分别用于表示五的倍数，且重复规则继续适用：I 表示 1，II 表示 2，III 表示 3，V 表示 5，VI 表示 6，VII 表示 7，等等；其他基数同理：X 表示 10，XX 表示 20，XXX 表示 30，L 表示 50，LXXX 表示 80；CC 表示 200，DCC 表示 700，等等。在第四次和第九次重复时，必须采用减法原则：将较小的基数符号置于较大基数符号之前，例如：IV 表示 4，IX 表示 9，XL 表示 40，XC 表示 90，CD 表示 400，CM 表示 900。

此外，对于大于 10 的进制，我们使用 A 表示 10，B 表示 11，依此类推。

请帮助沙普尔俘获瓦莱里安，让和平重回波斯，尤其是亚美尼亚！

The first line contains two integers a and b (2 ≤ a, b ≤ 25). Only b may be replaced by an R which indicates Roman numbering system.

The next line contains a single non-negative integer c in base a which may contain leading zeros but its length doesn't exceed 103.

It is guaranteed that if we have Roman numerals included the number would be less than or equal to 300010 and it won't be 0. In any other case the number won't be greater than 101510.

第一行包含两个整数 $a$ 和 $b$（$2 \leq a, b \leq 25$）。仅 $b$ 可能被替换为字母 R，表示罗马数字系统。

下一行包含一个在 $a$ 进制下的非负整数 $c$，该数可能含有前导零，但其长度不超过 $10^3$。

保证：若输入中包含罗马数字，则该数的十进制值不超过 $3000_{10}$ 且不为 $0$；在其他情况下，该数的十进制值不超过 $10^{15}_{10}$。

Write a single line that contains integer c in base b. You must omit leading zeros.

输出一行，包含整数 c 在 b 进制下的表示。你必须省略前导零。

You can find more information about roman numerals here: http://en.wikipedia.org/wiki/Roman_numerals

你可以在以下网址找到有关罗马数字的更多信息：http://en.wikipedia.org/wiki/Roman_numerals