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 <cmath>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define RFOR(i, a, b) for (int i = a; i > b; --i)
#define REP(i, n) for (int i = 0; i < n; ++i)

const int kMaxN = 100000;

string s;
int n;
int lr[kMaxN][2];
string ans = "";

int num_from_s[kMaxN];
int dif_s[kMaxN+1];
int sum[kMaxN+1];

class DisjointSet {
 public:
  vector<int> rank, p;

  DisjointSet();
  DisjointSet(int size) {
    rank.resize(size, 0);
    p.resize(size, 0);
    REP(i, size) { MakeSet(i); }
  }
  void MakeSet(int x) {
    p[x] = x;
    rank[x] = 0;
  }

  bool Same(int x, int y) { return FindSet(x) == FindSet(y); }
  void Unite(int x, int y) { Link(FindSet(x), FindSet(y)); }
  void Link(int x, int y) {
    if (rank[x] > rank[y]) {
      p[y] = x;
    } else if (rank[x] < rank[y]) {
      p[x] = y;
    } else {
      p[x] = y;
      ++rank[y];
    }
  }
  int FindSet(int x) {
    if (x != p[x]) { p[x] = FindSet(p[x]); }
    return p[x];
  }
};

int main() {
  cin >> s;
  cin >> n;
  REP(i, n) { cin >> lr[i][0] >> lr[i][1]; }

  REP(i, s.length()) { num_from_s[i] = s[i] - 97; }
  REP(i, s.length()+1) {
    if (i == 0) {
      dif_s[i] = num_from_s[i];
    } else if (i == s.length()) {
      dif_s[i] = (0 - num_from_s[i-1] + 26) % 26;
    } else {
      dif_s[i] = (num_from_s[i] - num_from_s[i-1] + 26) % 26;
    }
  }

  DisjointSet ds(s.length()+1);
  REP(i, s.length()+1) {
    if (i < s.length()-i) {
      ds.Unite(i, s.length()-i);
    } else {
      break;
    }
  }
  REP(i, n) { ds.Unite(lr[i][0]-1, lr[i][1]); }

  fill(sum, sum+s.length()+1, 0);
  REP(i, s.length()+1) { sum[ds.FindSet(i)] += dif_s[i]; }
  ans = "YES";
  REP(i, s.length()+1) {
    if (sum[i]%26 != 0) {
      ans = "NO";
      break;
    }
  }

  cout << ans << endl;
  return 0;
}