#include using namespace std; #define rep(i,n) for (int i = 0; i< (n); ++i) #define repi(i, a, b) for (int i = (a); i < (b); ++i) #define all(x) (x).begin(), (x).end() #define fore(i, a) for(auto &i:a) using ll = long long; //https://yukicoder.me/problems/no/3082 //b:999999797, 999999883, 1000000007, 1000000009, 2147483647, 2147771771 struct roling_hash{ vector H, B; ll n, b, mod; string s; roling_hash(string s_,ll b_, ll mod_){ s = s_;b = b_; mod = mod_; n = s.size()+1; H.assign(n,0); B.assign(n,0); H[0] = 0; B[0] = 1; repi(i, 1, n){ H[i] = (b*H[i-1]%mod+s[i-1])%mod; B[i] = B[i-1]*b%mod; } } ll get_hash(ll l,ll r){ return (H[r+1] - B[r-l+1]*H[l]%mod+mod)%mod; } ll get_hash(string t){ ll res=0; ll sz = t.size(); rep(i, sz){ res += B[sz-1-i]*t[i]%mod; res %= mod; } return res; } }; long long random_large_ll(ll m, ll M) { static std::random_device rd; static std::mt19937_64 gen(rd()); std::uniform_int_distribution dist(m, M); return dist(gen); } ll inverse(ll mod, ll val){ ll x[2] = {mod, val}; ll a[2] = {1, 0}; ll i; for(i = 0; x[!i]; i ^= 1){ a[!i] -= x[i] / x[!i] * a[i]; x[i] = x[i] % x[!i]; } if(!i) a[!i] += mod; return a[!i]; } void solve(){ ll k; cin >> k; ll h1=0,h2=0; ll b = random_large_ll(2, 100100100); ll mod = 1000000009; string _(200001, '*'); roling_hash HS(_,b,mod); ll bx=1; vector s(k); vector t(k); rep(i, k)cin >> s[i] >> t[i]; vector db1(61); db1[0] = b; rep(i, 60){ db1[i+1] = db1[i]*db1[i]; db1[i+1] %= mod; } rep(i, k){ ll sz = s[i].size(); string rev = s[i]; reverse(all(rev)); ll bs = 1; rep(j, 61){ if((sz >> j) & 1){ bs*=db1[j]; bs%=mod; } } ll temp1 = HS.get_hash(s[i]); ll temp2 = HS.get_hash(rev); vector db2(61); db2[0] = bs; rep(j, 60){ db2[j+1] = db2[j]*db2[j]; db2[j+1] %= mod; } ll bst = 1; rep(j, 61){ if((t[i] >> j) & 1){ bst*=db2[j]; bst%=mod; } } ll p = (((1-bst+mod)%mod)*inverse(mod, (1-bs+mod)%mod))%mod; ll p1 = p*temp1%mod; ll p2 = p*temp2%mod; h1 *= bst; h1 %= mod; h1 += p1; h1 %= mod; p2 *= bx; p2 %= mod; h2 += p2; h2 %= mod; bx *= bst; bx %= mod; } cout << h1 <<" " << h2 << endl; if(h1 == h2)cout << "Yes" << endl; else cout << "No" << endl; } int main() { solve(); }