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:
#define taskname "test"

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long lli;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
int n, m;
string s;
int a[maxn];

vector<int> g[maxn];
bool vis[maxn];

void read_input()
{
    cin >> s;
    n = s.length() + 1;
    s = "a" + s + "a";
    cin >> m;
    for(int i = 0; i < m; ++i)
    {
        int l, r;
        cin >> l >> r;
        --l;
        g[l].push_back(r);
        g[r].push_back(l);
    }
}

void init()
{
    for(int i = 0; i < n; ++i)
        a[i] = s[i + 1] - s[i];
    for(int i = 0; i < n; ++i)
        g[i].push_back(n - i - 1);
}

void dfs(int u, int&tot)
{
    vis[u] = true;
    tot += a[u];
    for(int v: g[u])
        if(!vis[v]) dfs(v, tot);
}

void solve()
{
    fill(begin(vis), end(vis), false);
    for(int i = 0; i < n; ++i)
        if(!vis[i])
        {
            int tot = 0;
            dfs(i, tot);
            tot = (tot % 26 + 26) % 26;
            if(tot != 0)
            {
                cout << "NO\n";
                return;
            }
        }
    cout << "YES\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}