Symbolic Mathematics
Over the years software systems that can perform symbolic computation have improved considerably. Popular commercial systems currently include Mathematica and Maple; the Sage system is also freely available.
In this problem you're just going to implement a small part of such a system: the ability to compute (symbolically) f(g(x)) for the functions f(x) and g(x) expressed as polynomials with terms having non-negative integer exponents and integer coefficients.
Input
Polynomials will be expressed in the input and output as a sequence of terms followed immediately by the end of line. Each term consists of a plus or minus sign (except the first term doesn’t have a sign if it is plus), an integer coefficient (omitted if it is 1 and the term's exponent is non-zero), the lowercase letter 'x', a circumflex ('^'), and a non-negative exponent. If the exponent is 1, then the circumflex and the exponent are omitted. If the exponent is0, the 'x' is also omitted. Terms are given in decreasing order of their exponents, and each term must have a unique exponent. The table below shows a few example polynomials in this form along with their traditional algebraic representation.
The input will contain pairs of lines. The first line of each pair gives the polynomial f(x), and the second line of each pair gives the polynomial g(x). The input line after the last pair of polynomials will contain only an end of line character. Blanks and tabs will never appear in the input.
Coefficients and exponents in the input and output polynomials will never exceed 1000000 in absolute value.
Output
For each pair of input lines, display the input case number (1, 2, …), the input polynomials, and the polynomial representing the value of f(g(x)). Label the polynomials appropriately. Display a blank line after the output for each case. Follow the format shown in the samples below.