typedef frac type;
bool isZero(type x){
return x.x==0;
}
class Poly{
public:
vector<type>a={frac(0,1)};
Poly(){}
Poly(vector<type> b):a(b){}
ll n(){
return a.size()-1;
}
Poly operator = (type b){
this->a.resize(1);
this->a[0]=b;
return *this;
}
Poly operator = (vector<type> b){
this->a=b;
return *this;
}
friend ostream &operator << (ostream &o,const Poly &f){
for(int i=f.a.size()-1;~i;i--){
if(!i)cout<<"("<<f.a[i]<<")";
else cout<<"("<<f.a[i]<<")"<<"x^"<<i<<"+";
}
cout<<endl;
}
type coef(int i){
if(i>=a.size() || i<0)return frac(0,1);
return a[i];
}
type& operator [] (int i){
if(i>=a.size() || i<0)cout<<" Warning: Index out of range\n";
return a[i];
}
type operator () (type x){
type ans;
ans=0;
for(int i=n();~i;i--)ans=ans*x+a[i];
return ans;
}
Poly operator () (Poly x){
Poly ans,t;
for(int i=n();~i;i--){
t=Poly((vector<type>){a[i]});
ans=ans*x+t;
}
return ans;
}
Poly operator + (Poly &b){
Poly c;
c.a.resize(max(a.size(),b.a.size()));
for(int i=0;i<c.a.size();i++)c.a[i]=coef(i)+b.coef(i);
while(c.a.size()>1 && isZero(*(c.a.end()-1)))c.a.erase(c.a.end()-1);
return c;
}
Poly operator - (Poly &b){