#include #include #include using namespace std; using ll = long long; using i128 = __int128_t; struct frac{ i128 bunsi, bumbo; frac(i128 a, i128 b=1):bunsi(a), bumbo(b){ normalize(); } i128 gcd(i128 a, i128 b){ if(b==0) return a; else return gcd(b, a%b); } void normalize(){ if(bumbo<0) bunsi*=-1, bumbo*=-1; i128 g=gcd(max(bunsi, -bunsi), max(bumbo, -bumbo)); bunsi/=g, bumbo/=g; } frac& operator+=(const frac& other){ bunsi=bunsi*other.bumbo+other.bunsi*bumbo; bumbo*=other.bumbo; normalize(); return *this; } frac& operator-=(const frac& other){ bunsi=bunsi*other.bumbo-other.bunsi*bumbo; bumbo*=other.bumbo; normalize(); return *this; } frac& operator*=(const frac& other){ bunsi*=other.bunsi; bumbo*=other.bumbo; normalize(); return *this; } frac& operator/=(const frac& other){ bunsi*=other.bumbo; bumbo*=other.bunsi; normalize(); return *this; } frac operator+()const{ return *this; } frac operator-()const{ return frac(-bunsi, bumbo); } frac operator+(const frac& other)const{ frac ans=*this; return ans+=other; } frac operator-(const frac& other)const{ frac ans=*this; return ans-=other; } frac operator*(const frac& other)const{ frac ans=*this; return ans*=other; } frac operator/(const frac& other)const{ frac ans=*this; return ans/=other; } bool operator==(const frac& other)const{ return bunsi==other.bunsi&&bumbo==other.bumbo; } bool operator!=(const frac& other)const{ return !(*this==other); } bool operator<(const frac& other)const{ return (__int128)bunsi*other.bumbo<(__int128)other.bunsi*bumbo; } bool operator>(const frac& other) const { return other<*this; } bool operator<=(const frac& other)const{ return !(*this>other); } bool operator>=(const frac& other)const{ return !(*this=0) return p/q; else{ i128 pp=-p; return -(pp+q-1)/q; } } string to_string_128(i128 x){ if(x==0) return "0"; bool neg=false; if(x<0) neg=true, x=-x; string ans; while(x>0){ int p=x%10; ans.push_back((char)('0'+p)); x/=10; } if(neg) ans.push_back('-'); reverse(ans.begin(), ans.end()); return ans; } //i128用の入力オーバーロード istream& operator>>(istream& is, i128& x){ string s; cin >> s; bool neg=false; int i=0; if(s[0]=='-') neg=true, i++; i128 val=0; for(; i> n >> a >> b; vector k(n+1), pa(n+2, 1), pb(n+2, 1); for(auto&x:k) cin >> x; for(int i=1; i