ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1408. Polynomial Multiplication

Time limit: 1.0 second
Memory limit: 64 MB
This task is so simple. Calculate a product of two given polynomials.

Input

Two polynomials are written in the two input lines. Each line is not longer than 100 characters.
A polynomial consists of summands separated with operations symbols “+” and “-”. A summand consists of one or several multipliers separated with “*” symbols. The first multiplier may be a coefficient (it may be equal to zero). The coefficient might be with the leading zeros but it doesn’t exceed 100. The first coefficient might have a “-” sign. The other multipliers has a form of X^N or X, where X is a variable (small Latin letter), N – nonnegative integer that doesn’t exceed 100 (might be with the leading zeros). Multipliers, summands and operations symbols may be separated with spaces.

Output

in one line the product of those polynomials. The polynomial mustn’t have the similar summands (i.e. summands with the same set of multipliers differing only by coefficient). Each summand should have no two multipliers of the form X^N with the same X and N. Summands with zero coefficients and multipliers with zero powers should be omitted. Coefficient “1” of summand and power “1” of multiplier are to be omitted too. The exceptions are: the summand “1” and the polynomial “0”. Multipliers in one summand should be arranged in the alphabetic order. The summands in the sum are arranged in descending order by the sum of multipliers powers. If two sums of multipliers powers are equal then the first summand to be written down is the summand with a greater power of the variable a. If these powers are equal we consider the power of the variable b and so on. The spaces should be placed according to the sample.

Sample

input
x*y*z + 4*x^2*y - 2*z*y*y^4 - 1
x + 7*z
output
-2*x*y^5*z - 14*y^5*z^2 + 4*x^3*y + 29*x^2*y*z + 7*x*y*z^2 - x - 7*z
Problem Author: Vladimir Yakovlev
Problem Source: The 12th High School Pupils Collegiate Programming Contest of the Sverdlovsk Region (October 15, 2005)