#include #include using namespace std; struct frac{ using S=long long; S a,b; void normalize(){ S g=gcd(a,b); if (g==0) a=0,b=1; else a/=g,b/=g; if (b<0) a=-a,b=-b; } frac(S x){ a=x; b=1; } frac(S num,S den){ a=num; b=den; normalize(); } frac(){ a=0; b=1; } friend bool operator==(const frac &l,const frac &r){return l.a*r.b==l.b*r.a;} friend bool operator<(const frac &l,const frac &r){return frac(l.a*r.b-l.b*r.a).a<0;} friend bool operator<=(const frac &l,const frac &r){return !(l>r);} friend bool operator>(const frac &l,const frac &r){return frac(l.a*r.b-l.b*r.a).a>0;} friend bool operator>=(const frac &l,const frac &r){return !(l>n; vector a(n),b(n); for (int i=0;i>a[i]; for (int i=0;i>b[i]; map mp; ll sum=0; for (int i=0;i=0){ ans=p; break; } } cout<<(mint(ans.a)/mint(ans.b)).val()<