By the Fundamental Theorem of Algebra, we know that if we count roots with multiplicity, an $n$-th degree polynomial has exactly $n$ zeros (points where the function value is $0$) in the complex field. Given an integer-coefficient polynomial $F[x]$, all of its $n$ zeros are rational numbers (i.e., they can be written as the quotient of two integers). Furthermore, if we take all its non-zero zeros (where the function argument is not $0$ and the function value is $0$) and remove duplicates, we obtain $r$ distinct non-zero zeros, where the $i$-th non-zero zero can be expressed as:

$$\mathrm{sgn}_i \times \frac{q_i}{p_i}$$

In this expression, $\mathrm{sgn}_i$ represents the sign of the $i$-th zero, and $p_i$ and $q_i$ are two coprime positive integers.

Given $F[x]$, you are required to output its factored form.

Input

The input consists of a single line containing the polynomial $F[x]$.

The polynomial is guaranteed to be in the following form:

• $a_n x^n + a_{n-1}x^{n - 1} + \dots + a_1x + a_0$

The terms are ordered from highest degree to lowest. $a_i$ are integers. If $a_i$ is $0$, the 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 \neq 0$, the $1$ is not printed. It is guaranteed that $a_n \neq 0$.

See the sample input for details.

Output

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

• $a_n (x + u_1/v_1)^{t_1}(x + u_2/v_2)^{t_2} \dots (x + u_s/v_s)^{t_s}$

Where $u$ and $v$ are coprime, and $v$ is a positive integer.

The terms $u_i/v_i$ are arranged in descending order. If $u_i/v_i = 0$, the term is $x^{t_i}$. If $u_i/v_i$ is negative, the plus sign is omitted. If $v_i$ is $1$, the $/v_i$ is omitted.

If $t_i$ is $1$, the exponent $^{t_i}$ is omitted.

If $a_n$ is $\pm 1$, the $1$ is omitted.

See the sample output for details.

Examples

Input 1

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

Output 1

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

Input 2

-x^2+2x-1

Output 2

-(x-1)^2

Note

$p_i, q_i$ satisfy:

$$\prod_{i=1}^r p_i \le 10^6, \prod_{i=1}^r q_i \le 10^6$$