Problem Description

According to the fundamental theorem of algebra, if we count multiple roots, a polynomial of degree \( n \) has exactly \( n \) roots (points where the function value is 0) in the complex field. Given a polynomial \( F[x] \) with integer coefficients, its \( n \) roots are exactly rational numbers (i.e., can be written in the form of a fraction of two integers). If we remove duplicates from all non-zero roots (where the function argument is not 0 and the function value is 0), we can obtain \( r \) distinct non-zero roots, where the \( i \)-th non-zero root can be expressed as:

\[ sgn_i \times \frac{q_i}{p_i} \]

Here, \( sgn_i \) represents the sign of the \( i \)-th root, and \( p_i \) and \( q_i \) are coprime positive integers.

You are given \( F[x] \) and are asked to output its factored form.

Input Format

The input consists of a single line containing the polynomial \( F[x] \).

The polynomial is always in the following form:

\[ a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0 \]

The degrees are in descending order, where \( a_i \) are integers. If \( a_i \) is 0, that term is omitted; if \( a_i \) is negative, the preceding plus sign is omitted; if the absolute value of \( a_i \) is 1 and \( i \) is not 0, the 1 is not output. It is guaranteed that \( a_n \) is not 0.

See the sample input for details.

Output Format

Output a single line representing the factored form, in the following format:

\[ a_n (x + \frac{u_1}{v_1})^{t_1} (x + \frac{u_2}{v_2})^{t_2} \cdots (x + \frac{u_s}{v_s})^{t_s} \]

Here, \( u \) and \( v \) are coprime, and \( v \) is a positive integer.

The terms \( \frac{u_i}{v_i} \) are sorted in descending order. If \( \frac{u_i}{v_i} = 0 \), that term becomes \( x^{t_i} \); if \( \frac{u_i}{v_i} \) is negative, the plus sign is omitted; if \( v_i \) is 1, \( \frac{u_i}{v_i} \) is omitted.

If \( t_i \) is 1, \( ^{t_i} \) is omitted.

If \( a_n \) is \( \pm 1 \), the 1 is omitted.

See the sample output for details.

Sample Input and Output

Sample Input #1

8x^7-258x^5+2112x^3-512x

Sample Output #1

8(x-4)^2(x-1/2)x(x+1/2)(x+4)^2

Sample Input #2

-x^2+2x-1

Sample Output #2

-(x-1)^2

Notes

\( p_i, q_i \) satisfy:

\[ \prod_{i=1}^r p_i \leq 10^6, \prod_{i=1}^r q_i \leq 10^6 \]

见题面 Input 部分

见题面 Output 部分