Problem: Ringo has a string S.

He can perform the following N kinds of operations any number of times in any order.

* Operation i: For each of the characters from the L_i-th through the R_i-th characters in S, replace it with its succeeding letter in the English alphabet. (That is, replace `a` with `b`, replace `b` with `c` and so on.) For `z`, we assume that its succeeding letter is `a`.



Ringo loves palindromes and wants to turn S into a palindrome. Determine whether this is possible.

Constraints

* 1 \leq |S| \leq 10^5
* S consists of lowercase English letters.
* 1 \leq N \leq 10^5
* 1 \leq L_i \leq R_i \leq |S|

Input

Input is given from Standard Input in the following format:


S
N
L_1 R_1
L_2 R_2
:
L_N R_N


Output

Print `YES` if it is possible to turn S into a palindrome; print `NO` if it is impossible.

Examples

Input

bixzja
2
2 3
3 6


Output

YES


Input

abc
1
2 2


Output

NO


Input

cassert
4
1 2
3 4
1 1
2 2


Output

YES

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
 
#define VARNAME(x) #x
#define show(x) cerr << #x << " = " << x << endl
 
using namespace std;
using ll = long long;
 
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v)
{
    os << "sz:" << v.size() << "\n[";
    for (const auto& p : v) {
        os << p << ",";
    }
    os << "]\n";
    return os;
}
 
template <typename S, typename T>
ostream& operator<<(ostream& os, const pair<S, T>& p)
{
    os << "(" << p.first << "," << p.second
       << ")";
    return os;
}
 
 
constexpr ll MOD = (ll)1e9 + 7LL;
 
template <typename T>
constexpr T INF = numeric_limits<T>::max() / 10;
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    const int S = s.size();
    int N;
    cin >> N;
    vector<int> L(N);
    vector<int> R(N);
    vector<set<int>> Rs(S);
    for (int i = 0; i < N; i++) {
        cin >> L[i] >> R[i];
        L[i]--, R[i]--;
        if (R[i] < S / 2) {
            Rs[L[i]].insert(R[i]);
        } else if ((S - 1) / 2 < L[i]) {
            Rs[S - R[i] - 1].insert(S - L[i] - 1);
        } else if (L[i] + R[i] < S - 1) {
            Rs[L[i]].insert(S - R[i] - 2);
        } else if (L[i] + R[i] > S - 1) {
            Rs[S - R[i] - 1].insert(L[i] - 1);
        }
    }
    for (int l = 0; l < S; l++) {
        if (Rs[l].size() <= 1) {
            continue;
        }
        auto it = Rs[l].begin();
        while (true) {
            const auto prev = it;
            it++;
            if (it == Rs[l].end()) {
                break;
            } else {
                Rs[*prev + 1].insert(*it);
            }
        }
        const int r = *Rs[l].cbegin();
        Rs[l].clear();
        Rs[l].insert(r);
    }
 
    vector<int> value;
    for (int i = 0; i < S; i++) {
        value.push_back(s[i] - 'a');
    }
    show(value);
    const int size = S / 2;
    for (int i = 0; i < size; i++) {
        value[i] = (value[i] - value[S - i - 1] + 26) % 26;
    }
    show(value);
    vector<int> d(size + 1);
    d[0] = value[0];
    for (int i = 1; i < size; i++) {
        d[i] = (value[i] - value[i - 1] + 26) % 26;
    }
    d[size] = (26 - value[size - 1])%26;
    show(d);
 
    for (int l = 0; l < S; l++) {
        for (const int r : Rs[l]) {
            d[r + 1] = (d[r + 1] + d[l] + 26) % 26;
            d[l] = 0;
        }
    }
 
    for (int i = 0; i <= size; i++) {
        if (d[i] > 0) {
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
 
    return 0;
}