该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

dXqwq 是个讨厌写作业的女孩子。

今天，她学习了因式定理。作为例题，她的老师希望她能分解一个 n 次多项式 F(x)=i=0∑naixi，其中 ai 都是整数，且 an=1，a0=0。

形式化地来讲，你需要对输入的多项式找到 m 对整数 (bi,ci) 满足 F(x)=i=1∏m(x+bi)ci，且 bi 互不相同。输入保证这样的 (bi,ci) 存在。

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

对于输入，如果 ai>0，这一项的输入应该为 +aix^i，如果 ai=0 则没有输入，否则这一项为 -|ai|x^i；特别地，如果 i=1，输入中的 ^i 会被省略；如果 i=0，输入中的 x^i 会被省略；对于最高次项，会直接输入 x^n，不会输入额外的系数；例如 x3−x+1 的输入即为 x^3-1x+1。

对于输出，如果 bi<0，这一项的输出应该为 (x-|bi|)，否则这一项为 (x+bi)；而如果 ci>1 时，你需要再在后面输出 ^ci，ci=1 时则不需要；在每两个因式之间，你不需要输出乘号分隔。

Input Format

从文件 decompose.in 中读入数据。

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

Output Format

输出到文件 decompose.out 中。

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

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

(x+1)^3

Hint

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

		
	

	(x+1)^3
	

		
	

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

		
	

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

		
	

	见下发的 decompose3.in。
该样例满足测试点 7 的性质。
	

		
	

	见下发的 decompose3.ans。
该样例满足测试点 7 的性质。