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.

Input

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.

Output

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

Examples

Input

10 2
1


Output

1


Input

16 R
5


Output

V


Input

5 R
4


Output

IV


Input

2 2
1111001


Output

1111001


Input

12 13
A


Output

A

Note

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

Difficulty: HARD
Tags: Mathematics

Starter code:

Solutions:
(n, m) = input().split()
b = input()
if b.isdigit() and int(b) == 0:
	print(int(b))
elif n == m:
	print(b)
else:
	n = int(n)
	st1 = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25]
	st2 = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q']
	s = str(b)
	l = len(s)
	deci = 0
	j = 0
	for i in range(l - 1, -1, -1):
		ind = st2.index(s[j])
		deci += n ** i * ind
		j += 1
	if m == 'R':
		arr1 = [1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000]
		arr2 = ['I', 'IV', 'V', 'IX', 'X', 'XL', 'L', 'XC', 'C', 'CD', 'D', 'CM', 'M']
		Roman = ''
		for i in range(len(arr1) - 1, -1, -1):
			if deci >= arr1[i]:
				Roman += deci // arr1[i] * arr2[i]
				deci = deci % arr1[i]
		print(Roman)
	else:
		m = int(m)
		convert = ''
		while deci > 0:
			t = deci % m
			convert += st2[t]
			deci = deci // m
		convert = convert[::-1]
		print(convert)


(system_1, system_2) = input().split()
integer = int(input(), base=int(system_1))
if system_2 == '10' or integer == 0:
	print(integer)
	exit(0)
digits = []
alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
if system_2 != 'R':
	system_2 = int(system_2)
	while integer != 0:
		if system_2 < 10:
			digits.append(str(integer % system_2))
		elif integer % system_2 < 10:
			digits.append(str(integer % system_2))
		else:
			digits.append(alphabet[integer % system_2 - 10])
		integer = integer // system_2
	print(''.join(digits[::-1]))
else:
	roman = [1000, 'M', 900, 'CM', 500, 'D', 400, 'CD', 100, 'C', 90, 'XC', 50, 'L', 40, 'XL', 10, 'X', 9, 'IX', 5, 'V', 4, 'IV', 1, 'I']
	ans = ''
	while integer != 0:
		for i in range(len(roman) // 2):
			if integer >= roman[2 * i]:
				ans = ans + roman[2 * i + 1]
				integer = integer - roman[2 * i]
				break
	print(ans)


import sys
from array import array

def input():
	return sys.stdin.buffer.readline().decode('utf-8')
(a, b) = input().split()
a = int(a)
num = int(input().rstrip(), a)
if b != 'R':
	b = int(b)
	ans = []
	while num:
		rem = num % b
		if rem >= 10:
			ans.append(chr(65 + rem - 10))
		else:
			ans.append(str(rem))
		num //= b
	if not ans:
		ans.append(0)
	print(*ans[::-1], sep='')
else:
	ans = []
	ans.append('M' * (num // 1000))
	num %= 1000
	if num >= 500:
		if num >= 900:
			ans.append('CM')
			num -= 900
		else:
			ans.append('D' + 'C' * ((num - 500) // 100))
			num %= 100
	if num >= 100:
		if num >= 400:
			ans.append('CD')
			num -= 400
		else:
			ans.append('C' * (num // 100))
			num %= 100
	if num >= 50:
		if num >= 90:
			ans.append('XC')
			num -= 90
		else:
			ans.append('L' + 'X' * ((num - 50) // 10))
			num %= 10
	if num >= 10:
		if num >= 40:
			ans.append('XL')
			num -= 40
		else:
			ans.append('X' * (num // 10))
			num %= 10
	if num >= 5:
		if num >= 9:
			ans.append('IX')
			num -= 9
		else:
			ans.append('V' + 'I' * (num - 5))
			num = 0
	if num > 0:
		if num == 4:
			ans.append('IV')
		else:
			ans.append('I' * num)
	print(*ans, sep='')


def main():

	def intToRoman(num):
		pattern = {'0': '', '1': 'a', '2': 'aa', '3': 'aaa', '4': 'ab', '5': 'b', '6': 'ba', '7': 'baa', '8': 'baaa', '9': 'ac'}
		code = ['IVX', 'XLC', 'CDM', 'M__']
		ret = []
		for (i, x) in enumerate(reversed(str(num))):
			tmp = pattern[x]
			for (p, r) in zip('abc', code[i]):
				tmp = tmp.replace(p, r)
			ret.append(tmp)
		return ''.join(reversed(ret))
	encodeB = '0123456789ABCDEFGHIJKLMNO'
	decodeA = {x: i for (i, x) in enumerate(encodeB)}
	(a, b) = input().split()
	a = int(a)
	if b != 'R':
		b = int(b)
	c = sum((decodeA[x] * a ** i for (i, x) in enumerate(reversed(input().lstrip('0')))))
	if b == 'R':
		print(intToRoman(c))
		return
	ans = []
	while c:
		ans.append(encodeB[c % b])
		c //= b
	ans = ''.join(reversed(ans))
	if not ans:
		ans = 0
	print(ans)
main()


digs = [chr(c) for c in range(ord('0'), ord('9') + 1)]
digs += [chr(c) for c in range(ord('A'), ord('Z') + 1)]

def int2base(x, base):
	if x < 0:
		sign = -1
	elif x == 0:
		return digs[0]
	else:
		sign = 1
	x *= sign
	digits = []
	while x:
		digits.append(digs[x % base])
		x //= base
	if sign < 0:
		digits.append('-')
	digits.reverse()
	return ''.join(digits)

def int2roman(x):
	ints = (1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1)
	nums = ('M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I')
	result = ''
	for i in range(len(ints)):
		count = int(x / ints[i])
		result += nums[i] * count
		x -= ints[i] * count
	return result
x = input().split()
a = int(x[0])
roman = False
b = x[1]
if b[0] == 'R':
	roman = True
else:
	b = int(b)
na = int(input(), a)
if roman:
	print(int2roman(na))
else:
	print(int2base(na, b))


from sys import stdin, stdout

def first(number, pw):
	cnt = 0
	for i in range(len(number)):
		if number[i] >= 'A':
			cnt += (ord(number[i]) - 55) * pw ** (len(number) - i - 1)
		else:
			cnt += int(number[i]) * pw ** (len(number) - i - 1)
	return cnt

def second(number, pw):
	s = []
	if number:
		value = 1
	else:
		return '0'
	cnt = 0
	while value * pw <= number:
		value *= pw
		cnt += 1
	while cnt >= 0:
		for i in range(pw - 1, -1, -1):
			if value * i <= number:
				if i <= 9:
					s.append(str(i))
				else:
					s.append(chr(65 + i - 10))
				number -= value * i
				value //= pw
				cnt -= 1
				break
	return s
chouse1 = ['', 'I', 'II', 'III', 'IV', 'V', 'VI', 'VII', 'VIII', 'IX']
chouse10 = ['', 'X', 'XX', 'XXX', 'XL', 'L', 'LX', 'LXX', 'LXXX', 'XC']
chouse100 = ['', 'C', 'CC', 'CCC', 'CD', 'D', 'DC', 'DCC', 'DCCC', 'CM']
chouse1000 = ['', 'M', 'MM', 'MMM']
s = stdin.readline().split()
c = stdin.readline().strip()
if s[-1] != 'R':
	(a, b) = map(int, s)
	stdout.write(''.join(second(first(list(c), a), b)))
else:
	a = int(s[0])
	ans = ''
	value = first(list(c), a)
	if value >= 1000:
		ans += chouse1000[value // 1000]
		value %= 1000
	if value >= 100:
		ans += chouse100[value // 100]
		value %= 100
	if value >= 10:
		ans += chouse10[value // 10]
		value %= 10
	if value >= 1:
		ans += chouse1[value]
	stdout.write(ans + '\n')


numbers = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9, 'A': 10, 'B': 11, 'C': 12, 'D': 13, 'E': 14, 'F': 15, 'G': 16, 'H': 17, 'I': 18, 'J': 19, 'K': 20, 'L': 21, 'M': 22, 'N': 23, 'O': 24, 'P': 25, 'Q': 26, 'R': 27, 'S': 28, 'T': 29, 'U': 30, 'V': 31, 'W': 32, 'X': 33, 'Y': 34, 'Z': 35}
characters = {0: '0', 1: '1', 2: '2', 3: '3', 4: '4', 5: '5', 6: '6', 7: '7', 8: '8', 9: '9', 10: 'A', 11: 'B', 12: 'C', 13: 'D', 14: 'E', 15: 'F', 16: 'G', 17: 'H', 18: 'I', 19: 'J', 20: 'K', 21: 'L', 22: 'M', 23: 'N', 24: 'O', 25: 'P', 26: 'Q', 27: 'R', 28: 'S', 29: 'T', 30: 'U', 31: 'V', 32: 'W', 33: 'X', 34: 'Y', 35: 'Z'}

def ConvertToDecimal(number, base):
	newnumber = 0
	for digit in range(-1, 0 - len(number) - 1, -1):
		if numbers[number[digit]] >= int(base):
			return -1
		newnumber += numbers[number[digit]] * int(base) ** (0 - digit - 1)
	return newnumber

def ConvertToBase(number, base):
	newnumber = ''
	if number == 0:
		return '0'
	while number > 0:
		newnumber = characters[number % base] + newnumber
		number = number // base
	return newnumber

def ConvertToRoman(number):
	newnumber = ''
	for i in range(4, 0, -1):
		currentnumber = (number % 10 ** i - number % 10 ** (i - 1)) // 10 ** (i - 1)
		if currentnumber > 0:
			if i == 4:
				newnumber += 'M' * currentnumber
			elif i == 3:
				if currentnumber == 9:
					newnumber += 'CM'
				elif currentnumber >= 5:
					newnumber += 'D' + 'C' * (currentnumber - 5)
				elif currentnumber == 4:
					newnumber += 'CD'
				else:
					newnumber += 'C' * currentnumber
			elif i == 2:
				if currentnumber == 9:
					newnumber += 'XC'
				elif currentnumber >= 5:
					newnumber += 'L' + 'X' * (currentnumber - 5)
				elif currentnumber == 4:
					newnumber += 'XL'
				else:
					newnumber += 'X' * currentnumber
			elif i == 1:
				if currentnumber == 9:
					newnumber += 'IX'
				elif currentnumber >= 5:
					newnumber += 'V' + 'I' * (currentnumber - 5)
				elif currentnumber == 4:
					newnumber += 'IV'
				else:
					newnumber += 'I' * currentnumber
	return newnumber
(a, b) = [x for x in input().split()]
c = input()
if b == 'R':
	print(ConvertToRoman(ConvertToDecimal(c, int(a))))
else:
	print(ConvertToBase(ConvertToDecimal(c, int(a)), int(b)))


import string
digs = string.digits + string.ascii_uppercase

def int2base(x, base):
	if x < 0:
		sign = -1
	elif x == 0:
		return digs[0]
	else:
		sign = 1
	x *= sign
	digits = []
	while x:
		digits.append(digs[int(x % base)])
		x = int(x / base)
	if sign < 0:
		digits.append('-')
	digits.reverse()
	return ''.join(digits)
(a, b) = input().split()
c = input()
R = {1: 'I', 5: 'V', 10: 'X', 50: 'L', 100: 'C', 500: 'D', 1000: 'M'}
s = int(c, int(a))
if b != 'R':
	print(int2base(s, int(b)))
else:
	s = int(int2base(s, 10))
	M = s // 1000
	s -= 1000 * M
	C = s // 100
	s -= 100 * C
	X = s // 10
	s -= 10 * X
	I = s
	r = ''
	if M:
		r += M * 'M'
	if C:
		if C <= 3:
			r += C * 'C'
		elif C == 4:
			r += 'CD'
		elif C >= 5 and C < 9:
			r += 'D' + 'C' * (C - 5)
		elif C == 9:
			r += 'CM'
	if X:
		if X <= 3:
			r += X * 'X'
		elif X == 4:
			r += 'XL'
		elif X >= 5 and X < 9:
			r += 'L' + 'X' * (X - 5)
		elif X == 9:
			r += 'XC'
	if I:
		if I <= 3:
			r += I * 'I'
		elif I == 4:
			r += 'IV'
		elif I >= 5 and I < 9:
			r += 'V' + 'I' * (I - 5)
		elif I == 9:
			r += 'IX'
	print(r)


(a, b) = input().strip().split(' ')
c = input()
a = int(a)

def conv(num, b):
	convStr = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
	if num < b:
		return convStr[num]
	else:
		return conv(num // b, b) + convStr[num % b]

def write_roman(num):
	val = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
	syb = ['M', 'CM', 'D', 'CD', 'C', 'XC', 'L', 'XL', 'X', 'IX', 'V', 'IV', 'I']
	roman_num = ''
	i = 0
	while num > 0:
		for _ in range(num // val[i]):
			roman_num += syb[i]
			num -= val[i]
		i += 1
	return roman_num
t = int(c.lower(), a)
if b != 'R':
	print(conv(t, int(b)))
else:
	print(write_roman(t))


from collections import OrderedDict

def romanConverter(num):
	roman = OrderedDict()
	roman[1000] = 'M'
	roman[900] = 'CM'
	roman[500] = 'D'
	roman[400] = 'CD'
	roman[100] = 'C'
	roman[90] = 'XC'
	roman[50] = 'L'
	roman[40] = 'XL'
	roman[10] = 'X'
	roman[9] = 'IX'
	roman[5] = 'V'
	roman[4] = 'IV'
	roman[1] = 'I'

	def roman_num(num):
		for r in roman.keys():
			(x, y) = divmod(num, r)
			yield (roman[r] * x)
			num -= r * x
			if num > 0:
				roman_num(num)
			else:
				break
	return ''.join([a for a in roman_num(num)])
	pass

def int2base(x, base):
	digs = []
	if x == 0:
		return x
	while x:
		if x % base < 10:
			digs.append(str(x % base))
		else:
			digs.append(chr(ord('A') + x % base - 10))
		x //= base
	digs.reverse()
	return ''.join(digs)

def function():
	c = input()
	(a, b) = (int(c[:c.find(' ')]), c[c.find(' ') + 1:])
	c = input()
	c = int(c, base=int(a))
	if b == 'R':
		c = romanConverter(c)
	else:
		c = int2base(c, int(b))
	return c
	pass
print(function())


ab = input().split()
alphabet = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z']
try:
	a = int(ab[0])
except TypeError:
	a = alphabet.index(ab[0]) + 10
b = ab[1]
if b != 'R':
	b = int(b)
c = input()
c2 = ''
found = False
for i in c:
	if i != '0':
		found = True
	if found:
		c2 += i
c = c2
result = 0
for i in range(len(c)):
	try:
		result += int(c[i]) * a ** (len(c) - i - 1)
	except ValueError:
		result += (alphabet.index(c[i]) + 10) * a ** (len(c) - i - 1)
strresult = ''
if c == '':
	strresult = 0
elif b != 'R':
	while result != 0:
		if result % b < 10:
			strresult = str(result % b) + strresult
		else:
			strresult = alphabet[result % b - 10] + strresult
		result = result // b
else:
	while result != 0:
		if result >= 1000:
			strresult += 'M'
			result -= 1000
		elif result >= 900:
			strresult += 'CM'
			result -= 900
		elif result >= 500:
			strresult += 'D'
			result -= 500
		elif result >= 400:
			strresult += 'CD'
			result -= 400
		elif result >= 100:
			strresult += 'C'
			result -= 100
		elif result >= 90:
			strresult += 'XC'
			result -= 90
		elif result >= 50:
			strresult += 'L'
			result -= 50
		elif result >= 40:
			strresult += 'XL'
			result -= 40
		elif result >= 10:
			strresult += 'X'
			result -= 10
		elif result >= 9:
			strresult += 'IX'
			result -= 9
		elif result >= 5:
			strresult += 'V'
			result -= 5
		elif result >= 4:
			strresult += 'IV'
			result -= 4
		else:
			strresult += 'I'
			result -= 1
print(strresult)


import math
y = [i for i in input().split()]
a = int(y[0])
b = y[1]
c = input()

def btb(oldbase, newbase, num):
	n = reversed(str(num))
	s10 = 0
	p = 0
	for i in n:
		d = ord(i) - 48
		if d >= 10:
			d = ord(i) - 65 + 10
		s10 += d * oldbase ** p
		p += 1
	if newbase == 100:
		return s10
	n = s10
	r = ''
	if n == 0:
		r = '0'
	while n > 0:
		d = n % newbase
		if d >= 10:
			d = chr(65 + d - 10)
		r += str(d)
		n //= newbase
	r = list(reversed(r))
	return ''.join(r)
roman = {1: 'I', 4: 'IV', 5: 'V', 9: 'IX', 10: 'X', 40: 'XL', 50: 'L', 90: 'XC', 100: 'C', 400: 'CD', 500: 'D', 900: 'CM', 1000: 'M'}
roman = dict(reversed(list(roman.items())))
roman3 = {900: 'CM', 4: 'IV', 9: 'IX', 40: 'XL', 90: 'XC', 400: 'CD', 100: 'C', 500: 'D', 5: 'V', 1: 'I', 10: 'X', 50: 'L', 1000: 'M'}

def DTR(dec):
	r = ''
	while dec > 0:
		for (k, v) in roman.items():
			if dec >= k:
				r += v * (dec // k)
				dec %= k
		return r

def RTD(R):
	s10 = 0
	for (k, v) in roman3.items():
		if R.count(v) > 0:
			s10 += R.count(v) * k
			R = R.replace(v, '')
	return s10
if b == 'R':
	print(DTR(int(btb(a, 100, c))))
else:
	print(btb(a, int(b), c))