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 <vector>

const int N = 100001;

int n, m, l[N], r[N], diff[N], val[N], sum;
bool vis[N];
char s[N];
std::vector<int> graph[N];

void add_edge(int a, int b)
{
    graph[a].push_back(b);
    graph[b].push_back(a);
}

void dfs(int u)
{
    if (vis[u]) {
        return;
    }
    vis[u] = true;
    (sum += diff[u]) %= 26;
    for (auto v : graph[u]) {
        dfs(v);
    }
}

int main()
{
#ifdef LOCAL_JUDGE
    freopen("E.in", "r", stdin);
#endif
    scanf("%s", s);
    n = strlen(s);
    scanf("%d", &m);
    for (int i = 0; i < m; ++ i) {
        scanf("%d%d", l + i, r + i);
        l[i] --;
    }
    diff[0] = s[0] % 26;
    for (int i = 1; i < n; ++ i) {
        diff[i] = (s[i] % 26 + 26 - s[i - 1] % 26) % 26;
    }
    diff[n] = (26 - s[n - 1] % 26) % 26;
    for (int i = 0; i + i <= n; ++ i) {
        add_edge(i, n - i);
    }
    for (int i = 0; i < m; ++ i) {
        add_edge(l[i], r[i]);
    }
    bool ok = true;
    for (int i = 0; i < n && ok; ++ i) {
        if (!vis[i]) {
            sum = 0;
            dfs(i);
            ok &= !sum;
        }
    }
    puts(ok ? "YES" : "NO");
}