2411. Common Polynomial

输入格式

The input consists of multiple datasets. Each dataset constitutes a pair of input lines, each representing a polynomial as an expression defined below.

1. A primary is a variable x, a sequence of digits 0 – 9, or an expression enclosed within ( · · · ). Examples: x, 99, (x+1). 2. A factor is a primary by itself or a primary followed by an exponent. An exponent consists of a symbol ^ followed by a sequence of digits 0 – 9. Examples: x^05, 1^15, (x+1)^3. 3. A term consists of one or more adjoining factors. Examples: 4x, (x+1)(x-2), 3(x+1)^2. 4. An expression is one or more terms connected by either + or -. Additionally, the first term of an expression may optionally be preceded with a minus sign -. Examples: -x+1, 3(x+1)^2-x(x-1)^2.

Integer constants, exponents, multiplications (adjoining), additions (+) and subtractions/negations (-) have their ordinary meanings. A sequence of digits is always interpreted as an integer con-stant. For example, 99 means 99, not 9 × 9.

Any subexpressions of the input, when fully expanded normalized, have coefficients less than 100 and degrees of x less than 10. Digit sequences in exponents represent non-zero values.

All the datasets are designed so that a standard algorithm with 32-bit two’s complement integers can solve the problem without overflows.

The end of the input is indicated by a line containing a period.

输出格式

For each of the dataset, output GCM polynomial expression in a line, in the format below.

c0 x^p0 ± c1 x^p1 · · · ± cn x^pn

Where ci and pi (i = 0, . . . , n) are positive integers with p0 > p1 > · · · > pn , and the greatest common divisor of {ci | i = 0, · · · , n} is 1.

Additionally:

1. When ci is equal to 1, it should be omitted unless corresponding pi is 0, 2. x^0 should be omitted as a whole, and 3. x^1 should be written as x.

-(x^3-3x^2+3x-1)
(x-1)^2
x^2+10x+25
x^2+6x+5
x^3+1
x-1

x^2-2x+1
x+5
1