Background

Special for beginners, ^_^

Description

在负进制数中是用-R作为基数，例如-15（十进制）相当于110001（-2进制），并且它可以被表示为-2的幂级数的和数： 110001 = 1*(-2)^5 + 1*(-2)^4 + 0*(-2)^3 + 0*(-2)^2 + 0*(-2)^1 + 1*(-2)^0 设计一个程序,读入一个十进制数和一个负进制数的基数, 并将此十进制数转换为此负进制下的数。

Format

Input

每个测试点输入的每行有两个数据。 第一个是十进制数n（绝对值不超过4万）。 第二个是负进制数的基数−R（−20≤R≤−2）。

Output

输出此负进制数及其基数，若此基数超过10，则参照16进制的方式处理。

Samples

30000 -2
-20000 -2
28800 -16
-25000 -16

30000=11011010101110000(base-2)
-20000=1111011000100000(base-2)
28800=19180(base-16)
-25000=7FB8(base-16)

Limitation

1s, 1024KiB for each test case.