Description

In today’s math class, the teacher covered addition and multiplication of polynomials. Then a lot of exercises were assigned. Xiaoming didn’t want to spend too much time on the homework, so he decided to write a program to do it.

For example, compute the sum and product of the following two polynomials:

$xy^2z+31wx^3y^3z^{50}+s^3$
$v^2+s^3+3wx^3y^3$

Assume all variables are single uppercase letters, and all coefficients and exponents are constants and integers.

We use X^3 to denote the third power of $X$, and we separate the coefficient and different variables by spaces. For example, in X Y^2, there is a space between $X$ and $Y$. Below are two example polynomials; aside from these, there are no other spaces.

X Y^2 Z + 31 W X^3 Y^3 Z^50 + S^3
V^2 + S^3 + 3 W X^3 Y^3

Now, given two polynomials in the above format, compute their sum and product.

Input Format

The input consists of two lines, each being one polynomial. Each polynomial has at most $250$ characters. During computation, it is guaranteed that the coefficients and exponents of any intermediate results do not exceed the long integer range.

Output Format

Output two lines: the first line is the sum of the two polynomials, and the second line is their product. Like the input, combine like terms in the output. The output format is similar to the input format, except that all spaces must be removed, and within each term the variables must be ordered by ascending ASCII code (i.e., output X^3Y^2 instead of Y^2X^3). Additionally, order the terms by the exponent of variable A in ascending order; if the exponents of A are equal, then by the exponent of B in ascending order; and so on. Also make sure the output conforms to our usual mathematical writing conventions.

A + B
3 A + 4 A B^3 + C

C+B+4A+4AB^3
BC+AC+3AB+4AB^4+3A^2+4A^2B^3

Hint

Translated by ChatGPT 5