#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
string s;
vi in;
int f(int a){
	if(s[a]=='+'||a==0)return 1;
	else if(s[a]=='-')return -1;
	int out=0;
	bool h=false;
	while(a&&isdigit(s[a-1]))a--;
	if(a&&s[a-1]=='-')h=true;
	while(isdigit(s[a])){
		out*=10;
		out+=s[a]-'0';
		a++;
	}
	if(h)out*=-1;
	return out;
}
vi ya;
int m;
vi out;
int dfs(int a,int b){
	if(a==m){
		//out
		loop(i,1,m+1){
			ll q=0;
			vi tmp(m);
			rep(j,i)tmp[j]=1;
			sort(all(tmp));
			do{
				ll qq=1;
				rep(j,m)if(tmp[j])qq*=out[j];
				q+=qq;
			}while(next_permutation(all(tmp)));
//			cout<<q<<" "<<in[m-i]<<endl;
			if(q!=in[m-i])return 0;
		}
/*		
		ll q=1;
		rep(i,m)q*=out[i];
		if(q!=in[0])return 0;
		q=0;
		rep(i,m)q+=out[i];
		if(q!=in[m-1])return 0;
		q=0;
		rep(i,m)rep(j,m)if(i!=j)q+=out[i]*out[j];
//		rep(i,m)cout<<" "<<out[i];cout<<endl;
		if(q/2!=in[m-2])return 0;
//*/		
		
		sort(all(out));
		bool h=true;
		rep(i,m-1)if(out[i]==out[i+1])h=false;
		if(!h)return 0;
		rep(i,m)printf("(x%+d)",out[i]);//cout<<" "<<out[i];cout<<endl;
		cout<<endl;
		return 1;
	}
	rep(i,ya.size())if(abs(in[0])%abs(b*ya[i])==0){
		out[a]=ya[i];
		if(dfs(a+1,b*ya[i]))return 1;
		out[a]=0;
	}
	return 0;
}
int main(){
	cin>>s;
	s="1"+s;
	in=vi(6);
	int n=s.size();
	rep(i,n)if(s[i]=='x'){
		if(s[i+1]=='^')in[s[i+2]-'0']=f(i-1);
		else in[1]=f(i-1);
	}
	in[0]=f(n-1);
	m=5;
	while(in[m]==0)m--;
	out=vi(m);
//	rep(i,6)cout<<" "<<in[i];cout<<endl;
	loop(i,1,2010)if(abs(in[0])%i==0){
		ya.pb(i);
		ya.pb(-i);
	}
//	rep(i,ya.size())cout<<" "<<ya[i];cout<<endl;
	dfs(0,1);
}


/*int n,m;
vvi in;
double h;
struct UnionFind{
    vector<int> data;
    UnionFind(int size) : data(size, -1) {}
    bool unionSet(int x,int y){
        x=root(x);y=root(y);
        if(x==y)return 0;
        if(data[y]<data[x])swap(x,y);
        data[x]+=data[y],data[y]=x;
        return 1;
    }
    bool findSet(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0 ? x : data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};
double l,r;
bool f(){
	UnionFind uf(n);
	ll c=0,d=0;
	rep(i,m){
		double t=(double)in[i][2]/in[i][3];
		if(t<h){
			uf.unionSet(in[i][0],in[i][1]);
			c+=in[i][2];d+=in[i][3];
		}else{
			if(uf.findSet(in[i][0],in[i][1])==0){
				if((double)(c+in[i][2])/(d+in[i][3])<h)continue;
				cout<<c<<" "<<d<<endl;
				cout<<in[i][0]<<" "<<in[i][1]<<endl;
				uf.unionSet(in[i][0],in[i][1]);
				c+=in[i][2];d+=in[i][3];
			}
		}
	}
	cout<<l<<" "<<r<<" "<<h<<" "<<uf.size(0)<<endl;
	if(uf.size(0)==n)return true;
	return false;
}
int main(){
	cin>>n>>m;
	in=vvi(m,vi(4));
	rep(i,m)rep(j,4)cin>>in[i][j];
	rep(i,m)swap(in[i][2],in[i][3]);
	rep(i,m)rep(j,m)if(i!=j){
		if((double)in[i][3]/in[i][2]<(double)in[j][3]/in[j][2])swap(in[i],in[j]);
	}
	rep(i,m){rep(j,4)cout<<" "<<in[i][j];cout<<endl;}
	l=0,r=1e10+2;
	while(r-l>EPS){
		h=(l+r)/2;
		if(f())r=h;
		else l=h;
	}
	cout<<l<<" "<<r<<endl;
}
//*/
### Prompt

Your challenge is to write a cpp solution to the following problem:

Problem

Mr. ukuku1333 is a little sloppy, so when I expanded the product of the linear expressions of x, I couldn't figure out the original linear expression.
Given the nth degree polynomial of x, factor it into the product of the original linear expressions of x.

The nth degree polynomial of x is given by the following BNF.


<Polynomial>: = <Term> | <Polynomial> & plus; <Polynomial> | <Polynomial> − <Term>
<Term>: = x ^ <exponent> | <coefficient> x ^ <index> | <coefficient> x | <constant>
<Index>: = [2-5]
<Coefficient>: = [1-9] [0-9] *
<Constant>: = [1-9] [0-9] *


If the exponent and coefficient are omitted, it is regarded as 1.

Constraints

The input satisfies the following conditions.

* 2 ≤ n ≤ 5
* For any set of i, j such that 1 ≤ i <j ≤ m, where m is the number of terms in the given expression,
The degree of the i-th term is guaranteed to be greater than the degree of the j-th term
* It is guaranteed that the nth degree polynomial of x given can be factored into the product form of the linear expression of x.
* Absolute values ​​of coefficients and constants are 2 × 103 or less, respectively.
* The coefficient with the highest degree is 1, which is guaranteed to be omitted.
* The original constant term of each linear expression before expansion is guaranteed to be a non-zero integer
* It is guaranteed that the original constant terms of each linear expression before expansion are different.

Input

The input is given in the following format.


S


The string S representing the nth degree polynomial of x is given on one line.

Output

Factor S into the product of a linear expression of x, and output it in ascending order of the constant term.
Insert a line break at the end of the output.

Examples

Input

x^2+3x+2


Output

(x+1)(x+2)


Input

x^2-1


Output

(x-1)(x+1)


Input

x^5+15x^4+85x^3+225x^2+274x+120


Output

(x+1)(x+2)(x+3)(x+4)(x+5)


Input

x^3-81x^2-1882x-1800


Output

(x-100)(x+1)(x+18)

### Response

```cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<int,pii> pip;
typedef vector<pip>vip;
const double PI=acos(-1);
const double EPS=1e-7;
const int inf=1e8;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
string s;
vi in;
int f(int a){
	if(s[a]=='+'||a==0)return 1;
	else if(s[a]=='-')return -1;
	int out=0;
	bool h=false;
	while(a&&isdigit(s[a-1]))a--;
	if(a&&s[a-1]=='-')h=true;
	while(isdigit(s[a])){
		out*=10;
		out+=s[a]-'0';
		a++;
	}
	if(h)out*=-1;
	return out;
}
vi ya;
int m;
vi out;
int dfs(int a,int b){
	if(a==m){
		//out
		loop(i,1,m+1){
			ll q=0;
			vi tmp(m);
			rep(j,i)tmp[j]=1;
			sort(all(tmp));
			do{
				ll qq=1;
				rep(j,m)if(tmp[j])qq*=out[j];
				q+=qq;
			}while(next_permutation(all(tmp)));
//			cout<<q<<" "<<in[m-i]<<endl;
			if(q!=in[m-i])return 0;
		}
/*		
		ll q=1;
		rep(i,m)q*=out[i];
		if(q!=in[0])return 0;
		q=0;
		rep(i,m)q+=out[i];
		if(q!=in[m-1])return 0;
		q=0;
		rep(i,m)rep(j,m)if(i!=j)q+=out[i]*out[j];
//		rep(i,m)cout<<" "<<out[i];cout<<endl;
		if(q/2!=in[m-2])return 0;
//*/		
		
		sort(all(out));
		bool h=true;
		rep(i,m-1)if(out[i]==out[i+1])h=false;
		if(!h)return 0;
		rep(i,m)printf("(x%+d)",out[i]);//cout<<" "<<out[i];cout<<endl;
		cout<<endl;
		return 1;
	}
	rep(i,ya.size())if(abs(in[0])%abs(b*ya[i])==0){
		out[a]=ya[i];
		if(dfs(a+1,b*ya[i]))return 1;
		out[a]=0;
	}
	return 0;
}
int main(){
	cin>>s;
	s="1"+s;
	in=vi(6);
	int n=s.size();
	rep(i,n)if(s[i]=='x'){
		if(s[i+1]=='^')in[s[i+2]-'0']=f(i-1);
		else in[1]=f(i-1);
	}
	in[0]=f(n-1);
	m=5;
	while(in[m]==0)m--;
	out=vi(m);
//	rep(i,6)cout<<" "<<in[i];cout<<endl;
	loop(i,1,2010)if(abs(in[0])%i==0){
		ya.pb(i);
		ya.pb(-i);
	}
//	rep(i,ya.size())cout<<" "<<ya[i];cout<<endl;
	dfs(0,1);
}


/*int n,m;
vvi in;
double h;
struct UnionFind{
    vector<int> data;
    UnionFind(int size) : data(size, -1) {}
    bool unionSet(int x,int y){
        x=root(x);y=root(y);
        if(x==y)return 0;
        if(data[y]<data[x])swap(x,y);
        data[x]+=data[y],data[y]=x;
        return 1;
    }
    bool findSet(int x,int y){
        return root(x)==root(y);
    }
    int root(int x){
        return data[x]<0 ? x : data[x]=root(data[x]);
    }
    int size(int x){
        return -data[root(x)];
    }
};
double l,r;
bool f(){
	UnionFind uf(n);
	ll c=0,d=0;
	rep(i,m){
		double t=(double)in[i][2]/in[i][3];
		if(t<h){
			uf.unionSet(in[i][0],in[i][1]);
			c+=in[i][2];d+=in[i][3];
		}else{
			if(uf.findSet(in[i][0],in[i][1])==0){
				if((double)(c+in[i][2])/(d+in[i][3])<h)continue;
				cout<<c<<" "<<d<<endl;
				cout<<in[i][0]<<" "<<in[i][1]<<endl;
				uf.unionSet(in[i][0],in[i][1]);
				c+=in[i][2];d+=in[i][3];
			}
		}
	}
	cout<<l<<" "<<r<<" "<<h<<" "<<uf.size(0)<<endl;
	if(uf.size(0)==n)return true;
	return false;
}
int main(){
	cin>>n>>m;
	in=vvi(m,vi(4));
	rep(i,m)rep(j,4)cin>>in[i][j];
	rep(i,m)swap(in[i][2],in[i][3]);
	rep(i,m)rep(j,m)if(i!=j){
		if((double)in[i][3]/in[i][2]<(double)in[j][3]/in[j][2])swap(in[i],in[j]);
	}
	rep(i,m){rep(j,4)cout<<" "<<in[i][j];cout<<endl;}
	l=0,r=1e10+2;
	while(r-l>EPS){
		h=(l+r)/2;
		if(f())r=h;
		else l=h;
	}
	cout<<l<<" "<<r<<endl;
}
//*/
```