#pragma region Macros #pragma GCC target("avx", "avx2") #pragma GCC optimize("-O3", "unroll-loops") #include using namespace std; #if __has_include() #include #include #include #include #include #include #include #include #include #include #include using namespace atcoder; #endif using ll= long long; using ld= long double; using ull= unsigned long long; using i128= __int128; using pll= pair; using vi= vector; using vl= vector; using vd= vector; using vs= vector; using vi128= vector; using vb= vector; using vpll= vector; using vvi= vector; using vvl= vector; using vvd= vector; using vvs= vector; using vvi128= vector; using vvb= vector; using vvpll= vector; #if __has_include() using mint= modint1000000007; // using mint = modint998244353; #endif constexpr ll mod= 1e9 + 7; // constexpr ll mod= 998244353; #define ALL(x) (x).begin(), (x).end() #define _overload3(_1, _2, _3, name, ...) name #define REPBASE(i, a, b) for(ll(i)= (a), (i##_b)= (b); (i) < (i##_b); (i)++) #define RREPBASE(i, a, b) for(ll(i)= (a), (i##_b)= (b); (i) >= (i##_b); (i)--) #define LOOP(n) REPBASE(i##__COUNTER__##_##__LINE__, 0, n) #define REPB(i, n) REPBASE(i, 0, n) #define REPS(i, n) REPBASE(i, 1, n + 1) #define RREP(i, n) RREPBASE(i, n - 1, 0) #define RREPS(i, n) RREPBASE(i, n, 1) #define REP(...) _overload3(__VA_ARGS__, REPBASE, REPB, LOOP)(__VA_ARGS__) #define EACH(x, c) for(auto &x : c) #define PERM(p) \ sort(ALL(p)); \ for(bool(p##c)= 1; (p##c); (p##c)= next_permutation(ALL(p))) #define pb push_back #define eb emplace_back #define mp make_pair #define fi first #define se second #define likely(x) __builtin_expect(!!(x), 1) #define unlikely(x) __builtin_expect(!!(x), 0) template inline ll SZ(const T &x) { return x.size(); } ll TOPBIT(const ll &t) { return (t == 0 ? -1 : 63 - __builtin_clzll(t)); } ll BIT(const ll &n) { return (1LL << n); } template inline string YES(const T &n) { return (n ? "YES" : "NO"); } template inline string Yes(const T &n) { return (n ? "Yes" : "No"); } template inline string yes(const T &n) { return (n ? "yes" : "no"); } template inline void UNIQUE(T &v) { v.erase(unique(ALL(v)), v.end()); } template inline ll LB(const T &v, const U &x) { return distance(v.begin(), lower_bound(ALL(v), x)); } template inline ll UB(const T &v, const U &x) { return distance(v.begin(), upper_bound(ALL(v), x)); } template inline bool chmax(T &a, const T &b) { if(a < b) { a= b; return 1; } return 0; } template inline bool chmin(T &a, const T &b) { if(b < a) { a= b; return 1; } return 0; } const vpll dx4{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; const vpll dx8{{1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}, {-1, -1}, {0, -1}, {1, -1}}; #define VEC(name, size, ...) \ vector<__VA_ARGS__> name(size); \ IN(name) #define VV(name, h, w, ...) \ vector> name((h), vector<__VA_ARGS__>(w)); \ IN(name) #define LL(...) \ ll __VA_ARGS__; \ IN(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define LD(...) \ ld __VA_ARGS__; \ IN(__VA_ARGS__) #define I128(...) \ i128 __VA_ARGS__; \ IN(__VA_ARGS__) void _scan() {} template void _scan(pair &p) { _scan(p.fi), _scan(p.se); } template void _scan(T &a) { cin >> a; } void IN() {} template void IN(Head &head, Tail &...tail) { _scan(head); IN(tail...); } template inline istream &operator>>(istream &stream, vector &v) { EACH(x, v) stream >> x; return stream; } template inline ostream &operator<<(ostream &stream, const vector &v) { ll sz= SZ(v); REP(i, sz) { stream << v[i] << (i == sz - 1 ? "" : " "); } return stream; } template inline ostream &operator<<(ostream &stream, const vector> &v) { ll sz= SZ(v); REP(i, sz) { stream << v[i] << (i == sz - 1 ? "" : "\n"); } return stream; } template inline istream &operator>>(istream &stream, pair &p) { stream >> p.fi >> p.se; return stream; } template inline ostream &operator<<(ostream &stream, const pair &p) { stream << p.fi << " " << p.se; return stream; } template inline pair operator+(pair p, const pair &q) { p+= q; return p; } template inline pair &operator+=(pair &p, const pair &q) { p.fi+= q.fi; p.se+= q.se; return p; } template inline pair operator-(pair p, const pair &q) { p-= q; return p; } template inline pair &operator-=(pair &p, const pair &q) { p.fi-= q.fi; p.se-= q.se; return p; } template inline pair operator+(const pair &p) { return p; } template inline pair operator-(const pair &p) { return mp(-p.fi, -p.se); } inline i128 parse(string &s) { reverse(ALL(s)); i128 ret= 0; bool minus= 0; if(*(s.rbegin()) == '-') { minus= 1; s.pop_back(); } while(!s.empty()) { if('0' <= *(s.rbegin()) && *(s.rbegin()) <= '9') { ret= ret * 10 + *(s.rbegin()) - '0'; s.pop_back(); } else { break; } } reverse(ALL(s)); if(minus) ret*= -1; return ret; } inline string to_string(i128 val) { string ret= ""; bool minus= 0; if(val < 0) { minus= 1; val*= -1; } do { int digit= val % 10; ret+= to_string(digit); val/= 10; } while(val != 0); if(minus) ret+= "-"; reverse(ALL(ret)); return ret; } inline istream &operator>>(istream &stream, i128 &val) { string str; stream >> str; val= parse(str); while(!str.empty()) { stream.putback(*(str.rbegin())); str.pop_back(); } return stream; } inline ostream &operator<<(ostream &stream, const i128 &val) { stream << to_string(val); return stream; } inline void print() { cout << "\n"; } template inline void print(const Head &H, const Tail &...T) { cout << H; (cout << ... << (cout << " ", T)); cout << endl; } inline void debug_out() { cout << "\n"; } template inline void debug_out(const Head &H, const Tail &...T) { cout << H; (cout << ... << (cout << " ", T)); cout << endl; } #ifdef _DEBUG #define debug(...) debug_out(__VA_ARGS__) #else #define debug(...) #endif #pragma endregion /* safe_mod */ /* O(1) */ constexpr ll safe_mod(ll x, const ll &m= mod) { x%= m; if(x < 0) x+= m; return x; } /* modinv */ /* O(logmod) */ /* constraint: (a,m) == 1 */ /* requirement : safe_mod */ constexpr ll modinv(ll a, const ll &m= mod) { ll b= m, u= 1, v= 0; while(b) { ll t= a / b; a-= t * b; swap(a, b); u-= t * v; swap(u, v); } return safe_mod(u, m); } /* Chinese Remainder Theorem */ /* Garner's Algorithm */ /* O(|r|^2logmax(m)) */ /* requirement : safe_mod, modinv */ /* return (solution % mod,lcm(m) % mod) */ /* if no solution, return (0,0) */ pll Garner(vl r, vl ms, const ll &m= mod) { REP(i, SZ(r)) { REP(l, i) { ll g= gcd(ms[i], ms[l]); if(unlikely((r[i] - r[l]) % g != 0)) return {0, 0}; ms[i]/= g; ms[l]/= g; ll gi= gcd(ms[i], g), gl= g / gi; do { g= gcd(gi, gl); gi*= g, gl/= g; } while(g != 1); ms[i]*= gi, ms[l]*= gl; r[i]%= ms[i], r[l]%= ms[l]; } } ms.eb(m); vl coeffs(SZ(ms), 1); vl constants(SZ(ms), 0); REP(i, SZ(r)) { ll t= safe_mod((r[i] - constants[i]) * modinv(coeffs[i], ms[i]), ms[i]); REP(l, i + 1, SZ(ms)) { (constants[l]+= t * coeffs[l])%= ms[l]; (coeffs[l]*= ms[i])%= ms[l]; } } return {constants.back(), coeffs.back()}; } signed main() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(12); LL(N); vl X(N), Y(N); REP(i, N) cin >> X[i] >> Y[i]; pll ans= Garner(X, Y); ll zero= 1; REP(i, N) if(X[i] != 0) zero= 0; if(ans.se == 0) { print(-1); } else { if(zero) { print(ans.se); } else { print(ans.fi); } } }