C. Схватить Валериана
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Сейчас 260 год н. э., Шапур, будучи необычайно умным человеком, стал правителем Персии. Теперь он — Его Величество Шапур, Царь царей Ирана и не-Ирана.

Недавно римляне объявили войну Персии. Их цель была — захватить Армению. Естественно, Шапур победил их армию, и взял в плен генерала Филиппа. Теперь Шапур собирается схватить Валериана, римского императора.

Побежденный Валериан трусливо спрятался в комнате на самом верху башни своего замка. Чтобы схватить его, Шапур должен открыть много дверей с хитрыми замками. К счастью, Валериан слишком напуган чтобы делать сложные замки на дверях.

Каждый замок состоит из 4 частей. Первая часть представляет собой целое число a. Вторая часть — это либо целое число b, либо странный символ R. Третья часть — всегда целое число c, а четвертая часть — пустая, как-будто в ней нужно что-то записать. Открыв несколько дверей, Шапур быстро разгадал секрет замка. c — целое число в системе счисления a, чтобы открыть дверь, нужно записать его в системе счисления b. Плохая новость: R обозначает римскую систему счисления — непозиционную систему счисления, которая используется только в Римской империи. Так что открыть дверь не так просто!

Далее описывается эта странная система счисления, в которой даже нет нуля:

Римские числа основаны на семи символах: черта (обозначается буквой I) — единица, стропило (обозначается буквой V) — пять, крест (обозначается буквой X) — десять, C (как сокращение от Centum, рим. век) — сто, и так далее:

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

Символы повторяются несколько раз, чтобы получать числа, кратные степеням десяти (1, 10, 100, 1, 000). Символ V подставляется вместо пяти символов I: I 1, II 2, III 3, V 5, VI 6, VII 7 и так далее. То же самое для символов L и X, D и C: X 10, XX 20, XXX 30, L 50, LXXX 80; CC 200, DCC 700, и так далее. При повторении 4 или 9 символов, используется принцип вычитания: IV 4, IX 9, XL 40, XC 90, CD 400, CM 900.

В позиционных системах счисления для оснований больше 10 используется: A = 10, B = 11, и так далее.

Помогите Шапуру восстановить мир в Персии, и особенно в Армении.

Входные данные

Первая строка содержит два целых числа a и b (2 ≤ a, b ≤ 25). Только b может быть заменена символом R, что означает римскую систему счисления.

Следующая строка содержит неотрицательное целое число c в системе счисления a, которое может содержать лидирующие нули, но его длина не превосходит 103.

Гарантируется, что если используется римская система счисления, число будет меньше либо равно 300010, и не будет равно нулю. Иначе число будет не больше 101510.

Выходные данные

Выведите в единственной строке целое число c в системе счисления b. Не выводите лидирующие нули.

Примеры
Входные данные
10 2
1
Выходные данные
1
Входные данные
16 R
5
Выходные данные
V
Входные данные
5 R
4
Выходные данные
IV
Входные данные
2 2
1111001
Выходные данные
1111001
Входные данные
12 13
A
Выходные данные
A
Примечание

Подробно о римских числах: http://ru.wikipedia.org/wiki/Римские_цифры