Description

By the Fundamental Theorem of Algebra, counting multiplicity, a degree $n$ polynomial over the complex numbers has exactly $n$ zeros (points where the function value is $0$). You are given an integer-coefficient polynomial $F[x]$ whose $n$ zeros are all rational numbers (i.e., can be written as a ratio of two integers). If we deduplicate all nonzero zeros (the variable is not $0$ while the function value is $0$), we obtain $r$ distinct nonzero zeros, where the $i$-th nonzero zero can be written as:

$$sgn_i \times \frac{q_i}{p_i}$$

Here $sgn_i$ denotes the sign of the $i$-th zero, and $p_i$ and $q_i$ are two coprime positive integers.

You are given $F[x]$. Output its factorized form.

Input Format

The input contains exactly one line: the polynomial $F[x]$.

The polynomial is always given in the following form: $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$

The terms are in descending degree. Each $a_i$ is an integer. If $a_i = 0$, that term is omitted. If $a_i$ is negative, the preceding plus sign is omitted. If $|a_i| = 1$ and $i \ne 0$, the $1$ is not printed. It is guaranteed that $a_n \ne 0$. See the sample input.

Output Format

Output one line: the factorized form in the following format: $a_n (x + u_1 / v_1)^{t_1} (x + u_2 / v_2)^{t_2} \cdots (x + u_s / v_s)^{t_s}$

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

$u_i / v_i$ are sorted from largest to smallest. If $u_i / v_i = 0$, that factor is $x^{t_i}$. If $u_i / v_i$ is negative, the plus sign is omitted. If $v_i = 1$, then $/ v_i$ is omitted.

If $t_i = 1$, the exponent is omitted.

If $a_n = \pm 1$, the $1$ is omitted. See the sample output.

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

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

-x^2+2x-1

-(x-1)^2

Hint

测试点编号	多项式最高次数	互异零点数	系数范围(绝对值)
$1$	$2$		$\le 10$
$2$	$4$		$\le 100$
$3$	$7$		$\le 10^6$
$4$	$10$		$\le 10^7$
$5$	$12$		$\le 10^{16}$
$6$	$35$	$5$	$\le 10^{24}$
$7$	$39$		$\le 10^{68}$
$8$	$46$	$4$	$\le 10^{104}$
$9$	$80$	$2$	$\le 10^{12}$
$10$	$50$	$1$	$\le 10^{316}$

$p_i, q_i$ satisfy:

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

Translated by ChatGPT 5