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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define forn(i, a, n) for (int i = (int)(a); i < (int)(n); ++i)
#define ford(i, a, n) for (int i = (int)(n) - 1; i >= (int)(a); --i)
#define fore(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define fs first
#define sn second
#define trace(a)\
    for (auto i : a) cerr << i << ' ';\
    cerr << '\n'
#define eb emplace_back

#ifndef M_PI
const ld M_PI = acos(-1.0);
#endif

template<typename T>
inline void setmax(T& a, T b) {
    if (a < b) a = b;
}

template<typename T>
inline void setmin(T& a, T b) {
    if (a > b) a = b;
}

const ld eps = 1e-9;
const int INF = 2000000000;
const ll LINF = 1ll * INF * INF;
const ll MOD = 1000000007;

const int N = 1e5 + 10;
int p[N];
int n;

int get(int v) {
    return v == p[v] ? v : p[v] = get(p[v]);
}

vector<int> e[N];
int sum[N], used[N];

void addSum(int v, int val) {
    //cerr << val << ' ';
    int sgn = 2 * v > n;
    if (sgn) v = n - v;
    v = get(v);
    sum[v] += val;
}

void dfs(int u, bool& ok, vector<int>& sums, int color) {
    if (used[u]) {
        if (used[u] != color)
            ok = false;
        return;
    }
    used[u] = color;
    sums[color] += sum[u];
    for (int v : e[u])
        dfs(v, ok, sums, 3 - color);
}

bool solve(int v) {
    bool ok = true;
    vector<int> sums(3);
    dfs(v, ok, sums, 1);
    //cerr << "SOLVE:\n";
    //cerr << ok << ' ' << sums[1] << ' ' << sums[2] << '\n';
    /*
    if ((sums[1] + sums[2]) % 2)
        return false;
    if (ok && (sums[1] + sums[2]) % 26)
        return false;
    return true;
    */
    return (sums[1] + sums[2]) % 26 == 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    srand((unsigned)chrono::high_resolution_clock::now().time_since_epoch().count());
    string s;
    cin >> s;
    n = s.length();
    forn(i, 0, n) p[i] = i;
    int m;
    cin >> m;
    vector<pair<int, int>> eds;
    while (m--) {
        int l, r;
        cin >> l >> r;
        --l;
        int sgn = (2 * l > n) == (2 * r > n);
        if (2 * l > n) l = n - l;
        if (2 * r > n) r = n - r;
        //cerr << l << ' ' << r << ' ' << sgn << '\n';
        /*if (sgn) {
            l = get(l);
            r = get(r);
            p[l] = r;
        } else*/ eds.eb(l, r);
    }
    for (auto q : eds) {
        int u = get(q.fs), v = get(q.sn);
        if (u == v) continue;
        e[u].eb(v);
        e[v].eb(u);
    }
    addSum(0, s[0] - 'a');
    forn(i, 1, n)
        addSum(i, s[i] - s[i - 1]);
    addSum(n, 'a' - s[n - 1]);
    //if (n % 2 == 0)
    //    addSum(n / 2, s[n / 2] - s[n / 2 - 1]);
    for (int i = 0; 2 * i <= n; ++i)
        if (get(i) == i && !used[i])
            if (!solve(i)) {
                cout << "NO\n";
                return 0;
            }
    cout << "YES\n";
}