TThe 1998 22nd Annual acm International Collegiate
Programming Contest World Finals
sponsored by IBM

Problem H
Towers of Powers

File: towers.cc





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 ideanumber representations to model height. In this use fluctuations in problem you will compute several such number representations and show the they produce.skylines

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

         9    5      3      2
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

          2
         3   3+2    3    2
20000 = 3  +3   +2*3 +2*3 +2
As another example, consider n = 16647 and b = 2. The resulting expansion is
          2+1  2     2+1
         2   +2 +2  2     2
16647 = 2         +2    +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^0, b^2 instead of 1*b^2 and b instead of b^1 -- note that the caret symbol has been used here only to simplify the display of this page in HTML, your output will use the raised powers shown above and in the examples). 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 below.

Answers must be displayed using no more than 80 columns. Expansions requiring more than 80 columns must be split after the last complete term that ends before reaching 81 columns, i.e. after the last term residing on the lowest display line. A second set of display lines (and the same number of display lines) should be 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. There will not be more than one such split required for each input pair. 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. Follow this withe a blank line, the first display line. End each output with a line of 80 hyphens. All coefficients, bases, and exponents are to be displayed as standard base 10 integers. Be sure there are no extra spaces after the characters on each display line or the introductory line.

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
--------------------------------------------------------------------------------