通过代数基本定理，我们知道若计算重根，一个 $n$ 次的多项式在复数域内恰好有 $n$ 个零点(函数值为 $0$ 的点)。现给定一个整系数多项式 $F[x]$，它的 $n$ 个零点恰好都是有理数（即可以写成两个整数相除的形式）；同时，若我们把它所有的非零零点（函数自变量不为 $0$，函数值为 $0$）去重，则可以得到 $r$ 个互不相同的非零零点，其中第 $i$ 个非零零点可以被表示成下式：
$$\mathrm{sgn}_i \times \frac{q_i}{p_i}$$
式中 $\mathrm{sgn}_i$ 表示第 $i$ 个零点的符号，$p_i$ 和 $q_i$ 为互质的两个正整数。
现在告诉你 $F[x]$，要求你输出将他因式分解后的形式。
输入格式
输入只有一行，包含多项式 $F[x]$。
多项式一定是如下的形式：
- $a_n x$^$n + a_{n-1}x$^${n - 1} + ⋯ a_1x + a_0$
次数一定为从高到低，其中 $a_i$ 为整数，并且若 $a_i$ 为 $0$，则省略该项，若 $a_i$ 为负数，则省略之前的加号，若 $a_i$ 的绝对值为 1 且 $i$ 不为 $0$，则不输出 $1$，并且保证$a_n$不为 $0$.
详见样例输入。
输出格式
输出一行，表示因式分解后的形式，格式如下：
- $a_n (x + u_1/v_1)$^$t_1(x + u_2/v_2)$^$t_2 … (x + u_s/v_s)$^$t_s$
其中 $u$，$v$ 互质，且 $v$ 为正整数。
其中 $u_i/v_i$ 从大到小排列，若 $u_i/v_i = 0$ 则该项为 $x$^$t_i$，若 $u_i/v_i$ 为负数，则省略加号，若 $v_i$ 为 $1$，则省略 $/v_i$。
若 $t_i$ 为 $1$ 则省略^$t_i$。
若 $a_n$ 为 $±1$ 则将 $1$ 省略。
详见样例输出。
样例数据
样例 1 输入
8x^7-258x^5+2112x^3-512x
样例 1 输出
8(x-4)^2(x-1/2)x(x+1/2)(x+4)^2
样例 2 输入
-x^2+2x-1
样例 2 输出
-(x-1)^2
说明/提示
| 测试点编号 | 多项式最高次数 | 互异零点数 | 系数范围（绝对值） |
|---|---|---|---|
| $1$ | $2$ | $2$ | $≤ 10$ |
| $2$ | $4$ | $4$ | $≤ 100$ |
| $3$ | $7$ | $7$ | $≤ 10 ^ 6$ |
| $4$ | $10$ | $10$ | $≤ 10 ^ 7$ |
| $5$ | $12$ | $12$ | $≤ 10 ^ {16}$ |
| $6$ | $35$ | $5$ | $≤ 10 ^ {24}$ |
| $7$ | $39$ | $5$ | $≤ 10 ^ {68}$ |
| $8$ | $46$ | $4$ | $≤ 10 ^ {104}$ |
| $9$ | $80$ | $2$ | $≤ 10 ^ {12}$ |
| $10$ | $50$ | $1$ | $≤ 10 ^ {316}$ |
$p_i,q_i$ 满足：
$$\prod_{i=1}^rp_i≤10^6,\prod_{i=1}^rq_i≤10^6$$