Not an official ACM page
[1998 ACM Finals problem set | My ACM problem archive | my home page]
The 1998 22nd Annual acm International Collegiate
Programming Contest World Finals
sponsored by IBM


Problem H
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 complete base-b expansion of n 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

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

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

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 b0, b2 instead of 1*b2 and b instead of b1). 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, and a second set of display lines used to show the remaining portion of the expansion. The second part of the answer must begin in the same column as the previous part of the answer. See the sample output for an example.

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. No value will exceed the maximum signed integer size for the machine.

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 hyphens. All coefficients, bases, and exponents are to be displayed as standard base 10 integers. The expansion for each input pair will require at most two standard screen widths, allowing for indentation and splitting between terms of the expansion.

Sample Input

20000 3
16647 2
1000 12
85026244 3
0 
0

Output for the Sample Input

20000 in complete base 3:

          2
         3   3+2    3    2
20000 = 3  +3   +2*3 +2*3 +2
-------------------------------------------------------
16447 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
This page maintained by Ed Karrels.
Last updated September 8, 1999