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 <algorithm>
#include <vector>
#include <set>
#include <cstdlib>
#include <utility>
#include <cmath>
#include <queue>
#include <stack>
#include <cstring>

using namespace std;

#define ll long long

#ifndef ONLINE_JUDGE
#define debug(format, ...) fprintf(stderr, \
    "%s:%d: " format "\n", __func__, __LINE__,##__VA_ARGS__)
#else
#define debug(format, ...)
#define NDEBUG
#endif

int n, half;

char s[100005];
int uf[50015];
int val[50005];
int dif[50005];
int ans[50005];

int fin(int a)
{
    if (uf[a] == a) return a;
    return uf[a] = fin(uf[a]);
}

void un(int a, int b)
{
    a = fin(a); b = fin(b);
    if (a == b) return;
    uf[a] = b;
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    half = n / 2;
    for (int i = 1; i <= half + 3; i++) uf[i] = i;
    int q; scanf("%d", &q);
    for (int i = 1; i <= q; i++) {
        int l, r; scanf("%d%d", &l, &r);
        if (l <= n - r + 1) {
            /* towards left */
            if (r > half) r = n - r;
        } else {
            //printf("%d\n", ((half + 1) - l) * 2 + (n % 2));
            if (l < half + 1 + (n % 2)) l += ((half + 1) - l) * 2 + (n % 2);
            int nl = n - r + 1;
            int nr = n - l + 1;
            l = nl; r = nr;
        }
        //printf("%d %d\n", l, r);
        un(l, r + 1);
    }
    for (int i = 1; i <= half; i++) {
        val[i] = (s[i] - s[n-i+1] + 26) % 26;
    }
    for (int i = 1; i <= half + 1; i++) {
        dif[i] = (val[i] - val[i-1] + 26) % 26;
        ans[fin(i)] += dif[i];
        ans[fin(i)] %= 26;
    }
    for (int i = 1; i <= half + 1; i++) {
        if (ans[i]) {
            printf("NO"); return 0;
        }
    }
    printf("YES");
    return 0;
}