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 <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <utility>
#include <vector>

static const int MAXS = 1e5 + 4;
static const int MAXN = 1e5 + 3;

static int l;
static char s[MAXS];

static int n;
static std::vector<int> r[MAXS / 2];

static int d[MAXS / 2];
static int e[MAXS / 2];

int main()
{
    scanf("%s", s);
    l = strlen(s);
    scanf("%d", &n);
    for (int i = 0, lf, rg; i < n; ++i) {
        scanf("%d%d", &lf, &rg);
        --lf;
        if (lf >= (l + 1) / 2) lf = l - lf;
        if (rg >= (l + 1) / 2) rg = l - rg;
        if (lf > rg) std::swap(lf, rg);
        if (lf != rg) r[lf].push_back(rg);
    }

    int h = l / 2;
    for (int i = 0; i < h; ++i) d[i] = ((s[i] - s[l - i - 1]) % 26 + 26) % 26;

    // priority_queue<time, decrement>
    std::priority_queue<
        std::pair<int, int>,
        std::vector<std::pair<int, int>>,
        std::greater<std::pair<int, int>>
    > q;
    for (int i = 0; i < h; ++i) {
        e[i] = (i == 0 ? 0 : e[i - 1]);
        while (!q.empty() && q.top().first == i) {
            e[i] = (e[i] - q.top().second + 26) % 26;
            q.pop();
        }
        if (!r[i].empty()) {
            std::sort(r[i].begin(), r[i].end());
            r[i].resize(std::unique(r[i].begin(), r[i].end()) - r[i].begin());
            for (int j = 1; j < r[i].size(); ++j)
                r[r[i][j - 1]].push_back(r[i][j]);
            int j = r[i][0];
            int diff = (d[i] - e[i] + 26) % 26;
            if (diff != 0) {
                (e[i] += diff) %= 26;
                q.push({ j, diff });
            }
            r[i].clear();
        }
    }

    for (int i = 0; i < h; ++i)
        if (e[i] != d[i]) { puts("NO"); return 0; }

    puts("YES"); return 0;
}