#ifdef LOCAL #include "template.hpp" #else #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; namespace io { template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } template istream &operator>>(istream &is, array &v) { for (auto &x : v) is >> x; return is; } template istream& cin_tuple_impl(istream &is, T &t) { if constexpr (N < std::tuple_size::value) { auto &x = std::get(t); is >> x; cin_tuple_impl(is, t); } return is; } template istream &operator>>(istream &is, tuple &t) { return cin_tuple_impl(is, t); } template ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template ostream &operator<<(ostream &os, const array &v) { size_t n = v.size(); for (size_t i = 0; i < n; i++) { if (i) os << " "; os << v[i]; } return os; } template ostream& cout_tuple_impl(ostream &os, const T &t) { if constexpr (N < std::tuple_size::value) { if constexpr (N > 0) os << " "; const auto &x = std::get(t); os << x; cout_tuple_impl(os, t); } return os; } template ostream &operator<<(ostream &os, const tuple &t) { return cout_tuple_impl(os, t); } void in() {} template void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &...u) { cout << t; outr(u...); } void __attribute__((constructor)) _c() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } // namespace io using io::in; using io::out; using io::outr; #define SHOW(x) static_cast(0) using ll = long long; using D = double; using LD = long double; using P = pair; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using i128 = __int128; using u128 = unsigned __int128; using vi = vector; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) template using PQ = priority_queue>; template using minPQ = priority_queue, greater>; #define rep1(a) for(ll i = 0; i < a; i++) #define rep2(i, a) for(ll i = 0; i < a; i++) #define rep3(i, a, b) for(ll i = a; i < b; i++) #define rep4(i, a, b, c) for(ll i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(a) for(ll i = (a)-1; i >= 0; i--) #define rrep2(i, a) for(ll i = (a)-1; i >= 0; i--) #define rrep3(i, a, b) for(ll i = (b)-1; i >= a; i--) #define rrep4(i, a, b, c) for(ll i = (b)-1; i >= a; i -= c) #define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define for_subset(t, s) for (ll t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s))) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) #define SZ(v) ll(v.size()) #define MIN(v) *min_element(ALL(v)) #define MAX(v) *max_element(ALL(v)) #define LB(c, x) distance((c).begin(), lower_bound(ALL(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(ALL(c), (x))) template T SUM(const vector &v) { T res = 0; for(auto &&a : v) res += a; return res; } template vector> RLE(const vector &v) { if (v.empty()) return {}; T cur = v.front(); int cnt = 1; vector> res; for (int i = 1; i < (int)v.size(); i++) { if (cur == v[i]) cnt++; else { res.emplace_back(cur, cnt); cnt = 1; cur = v[i]; } } res.emplace_back(cur, cnt); return res; } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, true : false); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, true : false); } void YESNO(bool flag) { out(flag ? "YES" : "NO"); } void yesno(bool flag) { out(flag ? "Yes" : "No"); } int popcnt(int x) { return __builtin_popcount(x); } int popcnt(u32 x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(u64 x) { return __builtin_popcountll(x); } int popcnt_sgn(int x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); } int popcnt_sgn(ll x) { return (__builtin_parityl(x) & 1 ? -1 : 1); } int popcnt_sgn(u64 x) { return (__builtin_parityl(x) & 1 ? -1 : 1); } int highbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); } int highbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int highbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); } int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); } int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); } template T get_bit(T x, int k) { return x >> k & 1; } template T set_bit(T x, int k) { return x | T(1) << k; } template T reset_bit(T x, int k) { return x & ~(T(1) << k); } template T flip_bit(T x, int k) { return x ^ T(1) << k; } template T popf(deque &que) { T a = que.front(); que.pop_front(); return a; } template T popb(deque &que) { T a = que.back(); que.pop_back(); return a; } template T pop(queue &que) { T a = que.front(); que.pop(); return a; } template T pop(stack &que) { T a = que.top(); que.pop(); return a; } template T pop(PQ &que) { T a = que.top(); que.pop(); return a; } template T pop(minPQ &que) { T a = que.top(); que.pop(); return a; } template ll binary_search(F check, ll ok, ll ng, bool check_ok = true) { if (check_ok) assert(check(ok)); while (abs(ok - ng) > 1) { ll mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return ok; } template double binary_search_real(F check, double ok, double ng, int iter = 60) { for (int _ = 0; _ < iter; _++) { double mid = (ok + ng) / 2; (check(mid) ? ok : ng) = mid; } return (ok + ng) / 2; } // max x s.t. b*x <= a ll div_floor(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b < 0); } // max x s.t. b*x < a ll div_under(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b - (a % b <= 0); } // min x s.t. b*x >= a ll div_ceil(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b > 0); } // min x s.t. b*x > a ll div_over(ll a, ll b) { assert(b != 0); if (b < 0) a = -a, b = -b; return a / b + (a % b >= 0); } // x = a mod b (b > 0), 0 <= x < b ll modulo(ll a, ll b) { assert(b > 0); ll c = a % b; return c < 0 ? c + b : c; } // (q,r) s.t. a = b*q + r, 0 <= r < b (b > 0) // div_floor(a,b), modulo(a,b) pair divmod(ll a, ll b) { ll q = div_floor(a,b); return {q, a - b*q}; } #endif struct LazyMontgomeryModInt64 { using mint = LazyMontgomeryModInt64; using i64 = int64_t; using u64 = uint64_t; using u128 = __uint128_t; static u64 mod; static u64 r; static u64 n2; static u64 get_r() { u64 ret = mod; for (int i = 0; i < 5; ++i) ret *= 2 - mod * ret; return ret; } static void set_mod(u64 mod_) { assert(mod_ < (1LL << 62)); assert((mod_ & 1) == 1); mod = mod_; r = get_r(); assert(r * mod == 1); n2 = -u128(mod) % mod; } u64 a; LazyMontgomeryModInt64() : a(0) {} LazyMontgomeryModInt64(const int64_t &b) : a(reduce(u128(b % mod + mod) * n2)){}; static u64 reduce(const u128 &b) { return (b + u128(u64(b) * u64(-r)) * mod) >> 64; } mint &operator+=(const mint &b) { if (i64(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } mint &operator-=(const mint &b) { if (i64(a -= b.a) < 0) a += 2 * mod; return *this; } mint &operator*=(const mint &b) { a = reduce(u128(a) * b.a); return *this; } mint &operator/=(const mint &b) { *this *= b.inverse(); return *this; } mint operator+(const mint &b) const { return mint(*this) += b; } mint operator-(const mint &b) const { return mint(*this) -= b; } mint operator*(const mint &b) const { return mint(*this) *= b; } mint operator/(const mint &b) const { return mint(*this) /= b; } bool operator==(const mint &b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } bool operator!=(const mint &b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } mint operator-() const { return mint() - mint(*this); } mint operator+() const { return mint(*this); } mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } mint inverse() const { assert(a != 0); return this->pow(mod-2); } friend ostream &operator<<(ostream &os, const mint &b) { return os << b.get(); } friend istream &operator>>(istream &is, mint &b) { i64 t; is >> t; b = LazyMontgomeryModInt64(t); return (is); } u64 get() const { u64 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static u64 get_mod() { return mod; } }; using m64 = LazyMontgomeryModInt64; typename m64::u64 m64::mod, m64::r, m64::n2; bool miller_rabin(ll n, const vector &witness) { m64::set_mod(n); int s = 0, t; ll d = n - 1; while (d % 2 == 0) d >>= 1, s++; for (ll a : witness) { if (n <= a) return true; m64 x = m64(a).pow(d); if (x != 1) { for (t = 0; t < s; t++) { if (x == n-1) break; x = x * x; } if (t == s) return false; } } return true; } bool primality_test(ll n) { if (n <= 1) return false; if (n <= 2) return true; if (n % 2 == 0) return false; if (n < 4759123141LL) return miller_rabin(n, {2, 7, 61}); else return miller_rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022}); } ll random_prime(ll lb, ll ub) { mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); uniform_int_distribution rand(lb, ub); ll q; while (!primality_test(q = rand(mt))); return q; } mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); int main() { int k; in(k); vector s(k); vector t(k); rep(i,k) in(s[i],t[i]); rep(_,3){ ll p = random_prime(1e13, 1e14); uniform_int_distribution rand(1, p-1); ll b = rand(mt); m64::set_mod(p); m64 hash = 0, rev_hash = 0; ll len = 0; rep(i,k){ ll m = SZ(s[i]); m64 ht = 0, htr = 0; rrep(j,m) ht = ht * b + (s[i][j]-'0'); rep(j,m) htr = htr * b + (s[i][j]-'0'); m64 bl = m64(b).pow(len); m64 bm = m64(b).pow(m); m64 bmt = bm.pow(t[i]); m64 xx = (bmt-1) / (bm-1); hash = hash + bl * ht * xx; rev_hash = rev_hash * bmt + htr * xx; ll tm = (t[i] % (p-1)) * m % (p-1); len = (len + tm) % (p-1); } if(hash != rev_hash){ out("No"); return 0; } } out("Yes"); }