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 <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define TRACE(x) cout << #x << " = " << x << endl
#define _ << " _ " <<

typedef long long llint;

const int MAX = 100100;

char s[MAX];
vector<int> v[MAX], g[MAX];

int main(void) {
  scanf("%s", s);
  int M;
  scanf("%d", &M);
  vector<int> a(M), b(M);
  REP(i, M) {
    scanf("%d %d", &a[i], &b[i]);
    --a[i], --b[i];
  }
  
  int N = strlen(s);
  if (N % 2) {
    int mid = N / 2;
    rotate(s + mid, s + mid + 1, s + N);
    N--;

    REP(i, M) {
      if (a[i] > mid) a[i]--;
      if (b[i] >= mid) b[i]--;
    }
  }

  assert(N % 2 == 0);
  int m = N / 2;
  REP(i, M) {
    if (a[i] > b[i]) continue;
    
    if (a[i] < m && b[i] >= m) {
      int na = N-a[i];
      int nb = N-b[i]-2;

      if (na <= b[i]) {
        a[i] = na;
      } else if (nb >= a[i]) {
        b[i] = nb;
      } else {
        continue;
      }
    }

    if (a[i] >= m) {
      int nb = N-a[i]-1;
      int na = N-b[i]-1;
      a[i] = na;
      b[i] = nb;
    }

    assert(0 <= a[i] && a[i] <= b[i] && b[i] < m);
    v[a[i]].push_back(b[i]);
    //    TRACE(a[i] _ b[i]);
  }

  vector<int> p_inc(m+1, 0);
  int cur_inc = 0;
  REP(i, m) {
    int need = (s[i] - s[N-i-1] + 26) % 26;
    assert(0 <= need && need < 26);
    cur_inc += p_inc[i];
    cur_inc %= 26;
    if (cur_inc < 0) cur_inc += 26;

    need = (need - cur_inc + 26) % 26;

    if (v[i].size() > 0) {
      sort(v[i].begin(), v[i].end());
      v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
      for (int j = 1; j < (int)v[i].size(); ++j) {
        v[v[i][j-1] + 1].push_back(v[i][j]);
      }

      int j = v[i][0];
      cur_inc += need;
      p_inc[j+1] -= need;
    } else {
      if (need != 0) {
        puts("NO");
        return 0;
      }
    }
  }

  puts("YES");
  return 0;
}