Towers of Powers

One of the many problems in computer-generated graphics is realistically modeling the ``orderly randomness'' of things like mountain ranges and city skylines. A new student intern at a graphics company had an idea--use fluctuations in number representations to model height. In this problem you will compute several such number representations and show the ``skylines'' they produce.

Let n be any positive integer, and let b be an integer greater than or equal to 2. The completebase - bexpansionofn is obtained as follows. First write the usual base-b expansion of n, which is just a sum of powers of b, each multiplied by a coefficient between 1 and b - 1, omitting terms with zero coefficients. For example, if n = 20000 and b = 3, the base-3 expansion of 20000 is given by

20000 = 3⁹ + 3⁵ + 2×3³ + 2×3² + 2

To obtain the complete base-b expansion, we apply the same procedure to the exponents until all numbers are represented in base b. For n = 20000 and b = 3 we would have

20000 = 3^3² + 3^{3 + 2} + 2×3³ + 2×3² + 2

As another example, consider n = 16647 and b = 2. The resulting expansion is

16647 = 2^{2^{2 + 1} + 2² + 2} + 2^{2^{2 + 1}} + 2² + 2 + 1

The rising and falling heights of the numbers form the number's ``skyline.''

For each pair of integers n and b in the input, display the complete base-b representation of n. Your display should use multiple output lines for different exponent heights. The display must begin with n = , followed by the expansion. Answers should use an asterisk (*) as the multiplication symbol between coefficients and powers of b. Zero terms must not be printed, and unnecessary coefficients and exponents must not be shown (for example, display 1 instead of b⁰, b² instead of 1*b² and b instead of b¹). To assist in accurately viewing the skyline of the number, the display must show one character (either a digit, +, or *) per column of the multi-line display; there must be no unnecessary spaces. The correct format is illustrated in the sample output shown below.

Answers must be displayed using no more than 80 columns. Expansions requiring more than 80 columns must be split between terms, into two or more sets of display lines to show the remaining portion of the expansion. The second and following parts of the answer must begin in the same column as the first part of the answer and should contain the same number of (possibly blank) lines. The split may only occur between terms of the number itself (the bottom line), not between terms in an exponent. See the sample output for an example. Note that each set of display lines starts with a blank line.

Input

Input is a sequence of pairs of integers, n and b, followed by a pair of zeroes. Each value for n will be positive, and each value for b will be greater than or equal to 2. All values will fit into 64 bits unsigned integers (the maximum is therefore 18446744073709551615).

Output

For each input pair, n and b, print the complete base-b expansion of n as described above. Print a line containing

n in complete base b:

preceding each expansion. Separate the output for consecutive pairs by a line of exactly 80 hyphens. All coefficients, bases, and exponents are to be displayed as standard base 10 integers.

Sample Input

Sample Output

20000 in complete base 3:

          2
         3   3+2    3    2
20000 = 3  +3   +2*3 +2*3 +2
--------------------------------------------------------------------------------
16647 in complete base 2:

          2+1  2     2+1
         2   +2 +2  2     2
16647 = 2         +2    +2 +2+1
--------------------------------------------------------------------------------
1000 in complete base 12:

           2
1000 = 6*12 +11*12+4
--------------------------------------------------------------------------------
85026244 in complete base 3:

             2           2         2         2         2       2       2
            3 +2*3+1    3 +2*3    3 +3+2    3 +3+1    3 +2    3 +1    3
85026244 = 3        +2*3      +2*3      +2*3      +2*3    +2*3    +2*3


               2*3+2  2*3+1    3
           +2*3     +3     +2*3 +3+1

Miguel Revilla 2004-09-17