【提高】因式分解

大家都学过因式分解，而我们今天要用编程的方法来解决问题！！

已知一个 $n$ 次多项式：

其中 $a_i$ 都是整数，且 $a_n=1$ 且 $a_0 \neq 0$。

你需要对多项式 $F(x)$ 找到 $m$ 对整数 $(b_i, c_i)$ 满足：

其中 $b_i$ 互不相同，输入保证存在答案。

多项式 $F(x)$ 将按照非 $0$ 项从高次到低次输入给你，你也需要将分解后的多项式按照 $b_i$ 从小到大输出，且需要将相同的因式用指数形式描述。

对于输入：

• 如果 $a_i > 0$，这一项的输入应该为 $+a_ix^i$
• 如果 $a_i=0$ 则没有输入
• 如果 $a_i < 0$，这一项为 $-|a_i|x^i$

特别地，如果 $i=1$，输入中的 ^i 会被省略。对于最高次项，会直接输入 $x_n$ 不会输入额外的系数，其他项如果系数为 $\pm1$ 可以省略 $1$；

例如 $x^3-x+1$ 的输入为 x^3-x+1

对于输出：

• 如果 $b_i < 0$，这一项的输出应该为 $(x-|b_i|)$
• 如果 $b_i \le 0$，这一项为 $(x+b_i)$
• 如果 $c_i > 1$ 时，你需要再在后面输出 ^ci，
• 如果 $c_i=1$ 则不需要输出 $c_i$，
• 在每两个因式之间，你不需要输出乘号分隔

输入格式

输入一行，代表给定的多项式。

输出格式

输出一行，代表分解后的多项式。

x^3+3x^2+3x+1

(x+1)^3

x^3+2x^2-5x-6

(x-2)(x+1)(x+3)

x+5

(x+5)

提示

【样例 1 解释】

• 在线因式展开计算器

【样例 3 解释】

• 即使只有 1 项，也不要省略括号

【数据范围】

所有输入都是整数 $1\le n \le 20， |a_0| \le 10^9$， 保证有解。

来源