PROB5: COMPUTER ALGEBRA

As junior member of the Computer Algebra System group, you get to work on arithmetic of integer polynomials.

INPUT: prob5.dat

The input file contains a sequence of polynomial addition and multiplication problems. Each problem has the form:


operator
operand1
operand2

Operator can be either + (add) or * (multiply). Each operand is a sequence of lines of the form


N
C(1) P(1)
C(2) P(2)
C(3) P(3)
.
.
.
C(N) P(N)

This represents the N-term polynomial


C(1)*x^P(1)+C(2)*x^P(2)+C(3)*x^P(3)+...+C(N)*x^P(N)

Each polynomial will have at least one term, each term will have an integer coefficient, with no restriction on magnitude. The powers will be non-negative, but also without restriction on magnitude. While the powers may repeat or be in any order in the input file, the powers must appear in strictly decreasing order in the output file. For example, the polynomial sum (x+3) + (-2x^2-5), followed by the product (2x+3)*0 would be represented in the input file by:

       column   111111111122222222223
       123456789012345678901234567890
line 1:+[EOL]
     2:2[EOL]
     3:1 1[EOL]
     4:3 0[EOL]
     5:2[EOL]
     6:-2 2[EOL]
     7:-5 0[EOL]
     8:[EOL]
     9:*[EOL]
    10:2[EOL]
    11:2 1[EOL]
    12:3 0[EOL]
    13:1[EOL]
    14:0 0[EOL]
      :[EOF]

OUTPUT: prob5.out

The output should be the corresponding sums and products, in the same format as the input. For the example input given above, the correct output would be:

       column   111111111122222222223
       123456789012345678901234567890
line 1:Program 5 by team 0[EOL]
     2:3[EOL]
     3:-2 2[EOL]
     4:1 1[EOL]
     5:-2 0[EOL]
     6:[EOL]
     7:1[EOL]
     8:0 0[EOL]
     9:End of program 5 by team 0[EOL]
      :[EOF]

NORMALIZATION NOTE

The only time a zero will appear as a coefficient in the output is when the polynomial is exactly zero. In this case, the polynomial will be represented as:

    1
    0 0