Description

We can represent a decimal number as the sum of each Arabic digit multiplied by a power of $10$ whose exponent is the position of that digit. For example, $123$ can be written as $1 \times 10^2+2\times 10^1+3\times 10^0$.

Similarly, a binary number can be written as the sum of each binary digit multiplied by a power of $2$ whose exponent is the position of that digit.

In general, any positive integer $R$ or negative integer $-R$ can be chosen as the base of a numeral system. If the base is $R$ or $-R$, the required digits are $0,1,\dots,R-1$.

For example, when $R=7$, the digits are $0,1,2,3,4,5,6$, regardless of whether the base is $R$ or $-R$. If the absolute value of the base exceeds $10$, letters are commonly used to represent digits greater than $9$. For instance, in base $16$, $A$ represents $10$, $B$ represents $11$, $C$ represents $12$, and so on.

In a negative-base system, $-R$ is used as the base. For example, $-15$ (in decimal) is equivalent to $(110001)_{-2}$ (base $-2$), and it can be written as a sum of powers of $2$:

$$(110001)_{-2}=1\times (-2)^5+1\times (-2)^4+0\times (-2)^3+0\times (-2)^2+0\times (-2)^1 +1\times (-2)^0$$

Design a program that reads a decimal integer and the base of a negative-base system, and converts the decimal number into that negative-base representation.

Input Format

Each line of input contains two values.

The first is the decimal integer $n$. The second is the base $R$ of the negative-base numeral system.

Output Format

Output the number in this negative-base system together with its base. If the absolute value of the base exceeds $10$, represent digits greater than $9$ using uppercase letters as in hexadecimal.

30000 -2

30000=11011010101110000(base-2)

-20000 -2

-20000=1111011000100000(base-2)

28800 -16

28800=19180(base-16)

-25000 -16

-25000=7FB8(base-16)

Hint

Constraints

For $100\%$ of the testdata, $-20 \le R \le -2$, $|n| \le 37336$.

Translated by ChatGPT 5