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:
#pragma comment(linker, "/STACK:512000000")
#define _CRT_SECURE_NO_WARNINGS
/*#if !defined(YCM) && 0
#define _FORTIFY_SOURCE 0
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx,tune=native")
#include <stdio.h>
#endif*/
//#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(bool);
void precalc();
clock_t start;
int main() {
#ifdef AIM
    freopen("/home/alexandero/ClionProjects/ACM/input.txt", "r", stdin);
    //freopen("/home/alexandero/ClionProjects/ACM/output.txt", "w", stdout);
    //freopen("out.txt", "w", stdout);
#else
    //freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
    cout.sync_with_stdio(0);
    cin.tie(0);
    precalc();
    cout.precision(10);
    cout << fixed;
    //cin >> t;
    int testNum = 1;
    while (t--) {
        //cout << "Case #" << testNum++ << ": ";
        //cerr << testNum << endl;
        solve(true);
        //cerr << testNum - 1 << endl;
    }
    cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
    cerr << "\n\n time: " << (clock() - start) / 1.0 / CLOCKS_PER_SEC << "\n\n";
#endif

    return 0;
}

//BE CAREFUL: IS INT REALLY INT?

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {}

//#define int li
//const int mod = 1000000007;

void solve(bool read) {
    string s;
    if (read) {
        cin >> s;
    } else {
        s = string(1000, 'a');
    }
    int n;
    if (read) {
        cin >> n;
    } else {
        n = 1000;
    }
    int is_odd = (int)s.length() % 2;
    int half = (int)s.length() / 2;
    int len = (int)s.length();
    vector<pair<int, int>> segs;
    for (int i = 0; i < n; ++i) {
        int l, r;
        if (read) {
            cin >> l >> r;
        } else {
            do {
                l = rand() % n + 1;
                r = rand() % n + 1;
            } while (l > r);
        }
        --l; --r;
        if (l >= half) {
            l = len - 1 - l;
            r = len - 1 - r;
            swap(l, r);
        }
        if (l == half) {
            assert(is_odd);
            continue;
        }
        if (is_odd && r == half) {
            --r;
        }
        if (r < half) {
            segs.push_back({l, r});
            continue;
        }
        if (is_odd) {
            if (half - l < r - half) {
                l = len - 1 - l;
                r = len - 1 - r;
                swap(l, r);
            }
            segs.push_back({l, len - 1 - r - 1});
            continue;
        }
        if (half - 1 - l < r - half) {
            l = len - 1 - l;
            r = len - 1 - r;
            swap(l, r);
        }
        segs.push_back({l, len - 1 - r - 1});
    }

    vector<vector<int>> starts(half);
    vector<int> diff(half);
    for (int i = 0; i < half; ++i) {
        diff[i] = (s[i] + 26 - s[len - 1 - i]) % 26;
    }
    for (int cur = 0; cur < segs.size(); ++cur) {
        auto item = segs[cur];
        if (item.second >= item.first) {
            starts[item.first].push_back(item.second + 1);
        }
    }
    vector<int> add(half + 1, 0);

    for (int i = 0; i < half; ++i) {
        make_unique(starts[i]);
        for (int j = 1; j < starts[i].size(); ++j) {
            starts[starts[i][j - 1]].push_back(starts[i][j]);
        }
        if (i) {
            add[i] += add[i - 1];
        }
        int need = (diff[i] - add[i] + 26) % 26;
        if (need) {
            if (starts[i].empty()) {
                cout << "NO\n";
                return;
            }
            add[i] += need;
            add[starts[i][0]] -= need;
        }
    }
    cout << "YES\n";
}