#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a co; Polynomial():co(1,1){} Polynomial(Int s):co(s,0){} Polynomial(vector co):co(co){} size_t size() const{ return co.size(); }; void shrink(){ while(co.size()>1u&&!co.back()) co.pop_back(); } void reduce(){ Int g=abs(co.back()); if(!g) return; for(Int c:co) if(c!=0) g=__gcd(g,abs(c)); if(co.back()<0) g*=-1; for(Int &c:co) c/=g; } void print(){ shrink(); reduce(); Int n=size(),flg=0; for(Int i=n-1;i>0;i--){ if(!co[i]) continue; flg=1; if(i!=n-1&&co[i]>0) cout<<"+"; if(co[i]==-1) cout<<"-"; else if(co[i]!=1) cout<0) cout<<"+"; cout< divide(const P &a) const{ Int n=size(),m=a.size(),s=n-m+1; if(s<0) return make_pair(P(1),*this); P div(s); P rest=*this; for(Int i=0;i0;j--) rest[n-(i+j)]-=a[m-j]*d; } return make_pair(div,rest); } P operator/(const P &a) const{return divide(a).first;}; P operator%(const P &a) const{return divide(a).second;}; }; Polynomial gcd(Polynomial a,Polynomial b){ a.shrink();a.reduce(); b.shrink();b.reduce(); if(a.size()>d; vector a(d+1); for(Int i=0;i<=d;i++) cin>>a[i]; vector b({0,-1,0,1}); Polynomial x(a),y(b); Polynomial z=x%y; z.shrink(); auto co=z.co; cout<