The well-known physicist Alfred E Neuman is working on problems that involve multiplying polynomials of x and y. For example, he may need to calculate

   8      3              5         3
(-x y + 9x  - 1 + y) * (x y + 1 + x )

yielding the answer

  13 2    11      8      6    5     5 2     3    3
-x  y  - x  y + 8x y + 9x  - x y + x y  + 8x  + x y - 1 + y

Unfortunately, such problems are so trivial that the great man's mind keeps drifting off the job, and he gets the wrong answers. As a consequence, several nuclear warheads that he has designed have detonated prematurely, wiping out five major cities and a couple of rain forests.

Write a program to perform such multiplications and save the world.

The file of input data will contain pairs of lines, none longer than 80 characters. Stop your program when no more input is available. Each input line contains a polynomial written without spaces and without any explicit exponentiation operator. Exponents are positive non-zero unsigned integers. Coefficients are also integers, but may be negative. Both exponents and coefficients are less than or equal to 100 in magnitude. Each term contains at most one factor in x and one in y (i.e., at most one term of x to a power and likewise for y). For example, an input file for the above problem might be:

        -x8y+9x3-1+y
        x5y+1+x3
        #

Your program must multiply each pair of polynomials in the input and print each product on a pair of lines, the first line containing all the exponents, suitably positioned with respect to the rest of the information, which is in the line below. See the representation above.

The following rules control the output format:

* Terms in the output line must be sorted in decreasing order of powers of x and, for a given power of x, in increasing order of powers of y.

* Factors of similar terms must be combined into a single term. For example,

           2 3      2 3                          2 3
        42x y  - 40x y      should be shown as 2x y .

* Terms with a zero coefficient must not be displayed.

* Coefficients equal to 1 are not to printed, except for the case of a constant term equal to 1.

* When the exponent is 1 (e.g., x to the first power), do not print the exponent

* Binary pluses and minuses (that is the pluses and minuses connecting terms in the output) have a single blank column both before and after.

* If the coefficient of the first output term is negative, it is preceded by a unary minus in the first column, with no intervening blank column. Otherwise, the coefficient itself begins in the first output column.

* The output can be assumed to fit into a single line of at most 80 characters in length.

* There are no blank lines printed between each pair of output lines.

* There are no blank space on the end of input lines

* There should be no blank spaces on the end of output lines.

The above example conforms to all those requirements.

Sample input:

-x8y+9x3-1+y
x5y+1+x3

Sample output:

  13 2    11      8      6   5     5 2     3    3
-x  y  - x  y + 8x y + 9x - x y + x y  + 8x  + x y - 1 + y

Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4):

        0x554 = 0101 0101 0100
        0x234 = 0010 0011 0100
Bit differences: xxx  xx

Since five bits were different, the Hamming distance is 5.

Input specifications:

N, B, D on a single line

Output specifications:

N codewords, sorted, in decimal, ten per line.

Sample input:

16 7 3

Sample output:

0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127

Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.

Given a number base B (2 <= B <= 20 base 10) that has been read from the file INPUT.DAT, print all the integers N (1 <= N <= 100 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on.

Print both the number and its square in base B.

Output specifications:

The table of integers and their palindromic squares

Sample input:

10

1 1
2 4
3 9
11 121
22 484
26 676

You've just be assigned the project of implemented a windowing interface. This windowing interface is fairly simple, and fortunately, you don't have to display the actual windows. There are 5 basic operations:

        1) Create a window
        2) Bring a window to the top
        3) Put a window to the bottom
        4) Destroy a window
        5) Output what percentage of a window is visible (i.e., isn't covered
           by windows above it).

In the input, the operations appear in the following format:

        Create window:               w(I,x,y,X,Y)
        Bring window to top:         t(I)
        Put window on bottom:        b(I)
        Destroy window:              d(I)
        Output percentage visible:   s(I)

The I is a unique identifier for each window, which is one character. The character can be any of 'a'..'z', 'A'..'Z', and '0'..'9'. No extra spaces will appear in the input.

(x,y) and (X,Y) are opposite corners of the window. When a window is created, it is put `on top'. You can't create a window with an identifier that is already in use, but you can destroy a window and then create a new one with the identifier of the destroyed window. Coordinates will be positive integers, and all windows will be of non-zero area (x != X and y != Y).

The program must work for any number of windows (limited by the identifiers, of course), and x and y coordinates between 1 and 32767 inclusive.

Input specifications:

The input file will consist of a sequence of commands to your interpreter. They will be listed one per line. Terminate the program when no more input is available.

Output specifications:

Output lines only for the s() commands. Of course, there might be several s() commands so the output should be a sequence of percentages, one per line, stating the percentage of the windows that are visible. The percentages should be rounded to 3 decimal places.

Sample input:

w(a,10,132,20,12)
w(b,8,76,124,15)
s(a)

Sample Output:

49.167%

Back to the index