Common Polynomial#5794

Common Polynomial

1 second

64 megabytes

Very easy

Math teacher Mr. Matsudaira is teaching expansion and factoring of polynomials to his students. Last week he instructed the students to write two polynomials (with a single variable $x$ ), and to report GCM (greatest common measure) of them as a homework, but he found it boring to check their answers manually. So you are asked to write a program to check the answers.

Hereinafter, only those polynomials with integral coefficients, called integral polynomials, are considered.

When two integral polynomials $A$ and $B$ are given, an integral polynomial $C$ is a common factor of $A$ and $B$ if there are some integral polynomials $X$ and $Y$ such that $A = C X$ A = CX and $B = C Y$ B = CY.

GCM of two integral polynomials is a common factor which has the highest degree (for $x$ , here); you have to write a program which calculates the GCM of two polynomials.

It is known that GCM of given two polynomials is unique when constant multiplication factor is ignored. That is, when $C$ and $D$ are both GCM of some two polynomials $A$ and $B$ , $p \times C = q \times D$ p \times C = q \times D for some nonzero integers $p$ and $q$ .

Input

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

A primary is a variable x, a sequence of digits $0$ – $9$ , or an expression enclosed within (...). Examples: x, 99, (x+1).
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.
A term consists of one or more adjoining factors. Examples: 4x, (x+1)(x-2), 3(x+1)^2.
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 constant. For example, 99 means $99$ , not $9 \times 9$ 9 \times 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.

Output

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

$c_{0} x^{p_{0}} \pm c_{1} x^{p_{1}} \dots \pm c_{n} x^{p_{n}}$ c_0 x^{p_0} \pm c_1 x^{p_1} \ldots \pm c_n x^{p_n}

Where $c_{i}$ c_i and $p_{i}$ p_i ( $i = 0, \dots, n$ i = 0, \ldots, n) are positive integers with $p_{0} > p_{1} > \dots > p_{n}$ p_0 > p_1 > \ldots > p_n, and the greatest common divisor of ${c_{i} ∣ i = 0, \dots, n}$ \{c_i | i = 0, \ldots, n\} is $1$ .

Additionally:

When $c_{i}$ c_i is equal to $1$ , it should be omitted unless corresponding $p_{i}$ p_i is $0$ ,
$x^{0}$ x^0 should be omitted as a whole, and
$x^{1}$ x^1 should be written as x.

Examples

Example 1