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 <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstring>
#include <queue>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <random>
#include <functional>

using namespace std;

#define F first
#define S second
#define pb push_back
#define epr(...) fprintf(stderr, __VA_ARGS__)
#define db(x) cerr << #x << " = " << x << endl
#define db2(x, y) cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n"; 
#define db3(x, y, z) cerr << "(" << #x << ", " << #y << ", " << #z << ") = (" << x << ", " << y << ", " << z << ")\n"
#define dbv(a) cerr << #a << ": "; for (auto& xxxx: a) cerr << xxxx << " "; cerr << endl;
#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)a.size()
#define pw(n) (1ll << (n))
#define equal equalll
#define less lesss

typedef double dbl;
typedef long long ll;
const int N = -1;
const int INF = 1.01e9;
const int SIGMA = 26;
typedef vector<int> vi;


void add(int& a, int b) {
    a = (a + b + SIGMA) % SIGMA;
}

int main() {
#ifdef HOME 
    assert(freopen("in", "r", stdin));
#endif
    string s;
    cin >> s;
    int m = s.size();
    int n;
    scanf("%d", &n);
    vector<pair<int,int>> b;
    for (int i = 0; i < n; i++) {
        int l, r;
        scanf("%d%d", &l, &r);
        l--;
        r--;
        if (r <= (m - 1) / 2) {
            b.pb({l, min(r, m / 2 - 1)}); 
        }
        else if (m / 2 <= l) {
            int L = max(l, m - m / 2);
            int R = r;
            L = m - 1 - L;
            R = m - 1 - R;
            swap(L, R);
            b.pb({L, R});
        }
        else {
            int p1 = l;  
            int p2 = m - 1 - r;
            //db3(i, p1, p2);
            if (p1 > p2) swap(p1, p2);
            if (p1 != p2) {
                b.pb({p1, p2 - 1});
            }
        }
    }
    int cur = 0;
    for (int i = 0; i < sz(b); i++) {
        if (b[i].F <= b[i].S) {
            b[cur++] = b[i];
        }
    }
    b.resize(cur);
    n = cur;
    //m = cur;


    //db(b.size());
    //for (auto x: b) {
        //db2(x.F, x.S);
    //}


    vector<int> diff(m / 2);
    for (int i = 0; i < m / 2; i++) {
        diff[i] = (s[i] - 'a' + SIGMA - (s[m - 1 - i] - 'a')) % SIGMA;
    }
    //dbv(diff);
    diff.pb(0);
    vector<int> pref(m / 2 + 1);
    //db("!!");
    pref[0] = diff[0]; 
    for (int i = 0; i < m / 2; i++) {
        pref[i + 1] = (diff[i + 1] - diff[i] + SIGMA) % SIGMA;
    }
    //dbv(pref);
    
    int len = m / 2;
    vector<vector<int>> e(len);

    for (auto x: b) {
        e[x.F].pb(x.S - x.F + 1);
    }
    //for (auto x: e) {
        //for (auto y: x) {
            //cerr << y << " ";
        //}
        //cerr << endl;
    //}
    //db(len);


    for (int i = 0; i < len; i++) {
        sort(all(e[i]));
        e[i].resize(unique(all(e[i])) - e[i].begin());
        for (int j = 0; j + 1 < sz(e[i]); j++) {
            e[i + e[i][j]].pb(e[i][j + 1] - e[i][j]);
        }
        if (pref[i] != 0) {
            //db(i);
            if (e[i].empty()) {
                puts("NO");
                return 0;
            } 
            add(pref[i + e[i][0]], pref[i]);
            pref[i] = 0;
            //dbv(pref);
        } 
    }
    for (int i = 0; i <= len; i++) {
        assert(pref[i] == 0);
    }
    puts("YES");

        


#ifdef HOME 
    epr("time = %d ms\n", (int)(clock() * 1000. / CLOCKS_PER_SEC));
#endif
    return 0;
}