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 <iostream>
#include <vector>
#include <set>

using namespace std;

void failure () {
  cout << "NO" << endl;
  exit(0);
}

typedef long long ll;

const int MOD = 26; // change if needed

struct Modint {
  ll val;
  
  Modint (ll _val = 0)
    : val(_val % MOD) {}

  Modint operator+ (Modint other) const {
    return Modint(val + other.val);
  }

  void operator+= (Modint other) {
    val += other.val;
    val %= MOD;
  }

  Modint operator- () const {
    return Modint(MOD - val);
  }

  Modint operator- (Modint other) const {
    return Modint(val + MOD - other.val);
  }

  void operator-= (Modint other) {
    val += MOD - other.val;
    val %= MOD;
  }

  Modint operator* (Modint other) const {
    return Modint(val * other.val);
  }

  void operator*= (Modint other) {
    val *= other.val;
    val %= MOD;
  }

  bool operator== (Modint other) const {
    return val == other.val;
  }

  bool operator!= (Modint other) const {
    return val != other.val;
  }
};

Modint exp (Modint a, int k) {
  if (k == 0) {
    return Modint(1);
  } else if (k % 2 == 0) {
    Modint half = exp(a, k / 2);
    return half * half;
  } else {
    return a * exp(a, k - 1);
  }
}

Modint inv (Modint a) {
  return exp(a, MOD - 2);
}

ostream& operator<< (ostream& out, Modint p) {
  out << p.val;
  return out;
}


typedef pair<int, int> interval;
#define l first
#define r second

const int MAX_Q = 1e5 + 5;

interval qs [MAX_Q];
set<int> *rs [MAX_Q];
Modint sub [MAX_Q];

Modint A [MAX_Q];
Modint B [MAX_Q];

set<int>* merge (set<int> *p, set<int> *q) {
  if (p->size() < q->size()) {
    swap(p, q);
  }

  for (auto it = q->begin(); it != q->end(); it++) {
    p->insert(*it);
  }
  return p;
}

int main () {
  ios::sync_with_stdio(false);

  string s;
  cin >> s;
  
  int qc;
  cin >> qc;
  
  for (int i = 0; i < qc; i++) {
    cin >> qs[i].l >> qs[i].r;
    qs[i].l--; qs[i].r--;
  }

  if ((int) s.size() % 2 == 1) {
    int mid = (int) s.size() / 2;
    string t;
    for (int i = 0; i < (int) s.size(); i++) {
      if (i != mid) {
        t += s[i];
      }
    }
    s = t;

    for (int i = 0; i < qc; i++) {
      if (qs[i].l > mid) {
        qs[i].l--;
      }

      if (qs[i].r >= mid) {
        qs[i].r--;
      }
    }
  }

  int n = s.size();
  int m = n / 2;

  for (int i = 0; i < n; i++) {
    rs[i] = new set<int> ();
  }

  for (int i = 0; i < qc; i++) {
    if (qs[i].l <= qs[i].r) {
      int l = qs[i].l;
      int r = qs[i].r;

      int flips = 0;
      if (l >= m) {
        l = n - l - 1;
        flips++;
      }
      if (r >= m) {
        r = n - r - 1;
        flips++;
      }
      if (l > r) swap(l, r);
      if (flips == 1) {
        r--;
      }

      if (l <= r) {
        rs[l]->insert(r);
      }
    }
  }

  for (int i = 0; i < m; i++) {
    A[i] = Modint(s[i] - 'a');
  }

  for (int i = 0; i < m; i++) {
    B[i] = Modint(s[n - i - 1] - 'a');
  }

  Modint cur (0);
  for (int i = 0; i < m; i++) {
    cur -= sub[i];
    Modint need = B[i] - (A[i] + cur);
    bool can = !rs[i]->empty();

    if (can) {
      int nl = *(rs[i]->begin()) + 1;
      rs[i]->erase(nl - 1);
      rs[nl] = merge(rs[i], rs[nl]);
      
      cur += need;
      sub[nl] += need;
    } else if (need != Modint(0)) {
      failure();
    }
  }

  cout << "YES" << endl;
}