#include #include #include #include using namespace std; using namespace atcoder; using ll = long long; using mint = modint998244353; using vi = vector; using vvi = vector; using vvvi = vector; using vll = vector; using vvll = vector; using vvvll = vector; using vmi = vector; using vvmi = vector; using vvvmi = vector; #define all(a) (a).begin(), (a).end() #define rep2(i, m, n) for (int i = (m); i < (n); ++i) #define rep(i, n) rep2(i, 0, n) #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) class RollingHash{ private: ll base1; ll base2; vector rh1; vector rh2; vector pow1; vector pow2; public: RollingHash(const string &s, ll b1, ll b2){ base1 = b1; base2 = b2; int len = s.size(); rep(i, len){ if(i==0){ pow1.push_back(1); pow2.push_back(1); rh1.push_back(mint(s[i] - '0')); rh2.push_back(mint(s[i] - '0')); continue; } pow1.push_back(pow1[i-1]*mint(b1)); pow2.push_back(pow2[i-1]*mint(b2)); rh1.push_back(mint(s[i] - '0') + rh1[i-1]*mint(b1)); rh2.push_back(mint(s[i] - '0') + rh2[i-1]*mint(b2)); } } pair getHash(int l, int r){// 0-indexed mint a = rh1[r]; mint b = rh2[r]; if(l > 0){ a -= rh1[l-1]*pow1[r-l+1]; b -= rh2[l-1]*pow2[r-l+1]; } return {a, b}; } }; mint sum(ll n, mint b){ return (mint(b).pow(n) - 1)/(b-1); } int main(){ ios::sync_with_stdio(false); std::cin.tie(nullptr); int k; cin >> k; vector> vp(k); mint len = 0; rep(i, k){ string s; ll t; cin >> s >> t; vp[i] = {s, t}; len += mint(s.length()) * mint(t); } ll b1 = 99824443, b2 = 100000007; mint b3 = 0, b4 = 0; mint nlen = len; rep(i, k){ auto [s, t] = vp[i]; nlen -= mint(s.length()) *mint(t); int l = s.length(); RollingHash rh = RollingHash(s, b1, b2); auto [c, d] = rh.getHash(0, s.length()-1); b3 += (c * sum(t, mint(b1).pow(l)))*mint(b1).pow(nlen.val()); b4 += (d * sum(t, mint(b2).pow(l)))*mint(b2).pow(nlen.val()); } mint b5 = 0, b6 = 0; mint rlen = len; drep(i, k){ auto [s, t] = vp[i]; rlen -= mint(s.length()) * mint(t); string u = s; int l = u.length(); reverse(all(u)); RollingHash rh = RollingHash(u, b1, b2); auto [c, d] = rh.getHash(0, u.length()-1); b5 += (c * sum(t, mint(b1).pow(l)))*mint(b1).pow(rlen.val()); b6 += (d * sum(t, mint(b2).pow(l)))*mint(b2).pow(rlen.val()); } if(b3.val() == b5.val() && b4.val() == b6.val()){ cout << "Yes" << endl; }else{ cout << "No" << endl; } return 0; }