21985_Conversions

The BINEG computer your company recently bought is using the negabinary (or base -2) system instead of the more common binary (or base 2) system. To use the beast, you need to convert your existing data to the new representation. And, in order for the output to make any sense for the rest of the world, you also have to translate it back to the more conventional system.

Your boss is a guy who likes to solve problems "once and for all". So, he has asked you to develop a universal converter , from any system (using positive or negative base) to any other (again, using positive or negative base), and it should work on numbers of almost any size as well.

More formally, for any B (positive or negative), the digits used to write numbers in base B are 0...|B|-1, and the sequence of digits A_NA_N-1...A₁A₀ always represents the value A_NB^N+A_N-1B^N-1+...+A₁B+A₀. The first letters of the Latin alphabet are used as digits after 9 in case |B| > 10.

The first line of the input contains two integers, B₁ and B₂ (2 ≤ |B₁|, |B₂| ≤ 16), where B₁ is the input base and B₂ is the output base. The second line of the file contains a non-negative integer value written in base B₁ that may consist of up to 100 digits. Only uppercase letters are used in case |B₁| > 10.

The output consist of exactly one line containing the value given on the second line of the input file, but represented in base B₂. Only uppercase letters should be used in case |B₂| > 10 and the output should have minimal length in any case.

sample #1
2 16
11111

sample #2
-2 16
11111

sample #1
1F

sample #2
B