Polynomial Factorization

We are given a polynomial (F(x)) with integer coefficients such that all its roots (with multiplicities) are rational numbers. In particular, suppose that the polynomial has degree (n) and can be written as (F(x)=a_nx^n+\cdots+a_0) with (a_n\ne0). It is guaranteed that every root is rational. In addition, if we remove the duplicate nonzero roots, then for each distinct nonzero root, say the (i^{th}), it can be expressed in its reduced form as

[ \text{sgn}_i \times \frac{q_i}{p_i}, ]

where (\text{sgn}_i) is the sign of the root and (p_i) and (q_i) are two coprime positive integers. Your task is to factorize (F(x)) completely into linear factors with integer coefficients and output it in the following form:

[ F(x)=A, x^{m_0} \prod_{i=1}^{r} (p_i,x - ; \text{sgn}_i,q_i)^{m_i}, ]

where:

• (A) is an integer constant obtained by adjusting the leading coefficient so that the factors inside the product have integer coefficients. In fact, if the original polynomial is written as (a_n\prod (x-r)), then for a nonzero root (r=\text{sgn}\frac{q}{p}) (in lowest terms) we use the factor ((p,x - ; \text{sgn},q)) so that (x-r = \frac{p,x-;\text{sgn},q}{p}). Thus, if the product of all denominators raised to the appropriate multiplicities is (D), then (A=a_n/D).
• (m_0) is the multiplicity of the root (0) (if any).
• For each nonzero distinct root, (m_i) is its multiplicity.

The input guarantees that (A) will be an integer. Notice that if a root (r) is positive (i.e. (\text{sgn}=+)), the corresponding factor is written as ((p,x - q)); if (r) is negative (i.e. (\text{sgn}=-)), the factor is ((p,x + q)).

Your program must output the fully factorized form as a single string.

Examples (whitespace is optional):

1. For (F(x)=2x^3-5x^2+2x), the factorization is

   1. Zero is a root with multiplicity 1.
   2. The other quadratic (2x^2-5x+2) factorizes as with roots (2) and (1/2). For (r=2=2/1) (positive) the factor is ((1,x - 2)) and for (r=1/2) the factor is ((2,x - 1)). The product of denominators is (1\times 2=2) so (A=2/2=1). Thus, one valid output is:

   1x(x-2)(2x-1)

2. For (F(x)=x^2-1), one valid output is:

   1*(x-1)*(x+1)

Input and output formats are described below.

inputFormat

The first line contains an integer (n) ((n\ge1)), the degree of the polynomial (F(x)). The second line contains (n+1) space-separated integers representing the coefficients (a_n, a_{n-1}, \dots, a_0) of the polynomial.

outputFormat

Output a single line containing the factorized form of (F(x)) as a string in the format:

Ax^(m0)(p1x -/+ q1)^(m1)...(prx -/+ qr)^(mr)

Note: If the exponent is 1, you may omit the exponent. There should be no extra spaces (except inside factors if needed).

sample

3
2 -5 2 0

1*x*(x-2)*(2*x-1)