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 __USE_MINGW_ANSI_STDIO 0
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define int ll
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define IN(a, b, x) (a<=x&&x<b)
#define MP make_pair
#define PB push_back
#ifdef int
const ll INF = (1LL<<60);
#else
const int INF = (1LL<<30);
#endif
const double PI = 3.14159265359;
const double EPS = 1e-12;
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

#define MAX_N 200000

class UnionFind {
private:
  // 親と木の深さ
  int par[MAX_N];
  int rank[MAX_N];
  int s[MAX_N];
  bool used[MAX_N];
public:
  UnionFind();
  UnionFind(int);
  int find(int x);
  void unite(int, int);
  bool same(int, int);
  int size(int);
  int group(int);
};

//MAX_Nで初期化
UnionFind::UnionFind() {
  for(int i=0; i<MAX_N; ++i) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素数nで初期化
UnionFind::UnionFind(int n) {
  for(int i=0; i<n; i++) {
    par[i] = i;
    rank[i] = 0;
    s[i] = 1;
  }
}

// 要素xの親を求める
int UnionFind::find(int x) {
  if(par[x] == x) return x;
  else return par[x] = find(par[x]);
}

// xとyの属する集合を併合
void UnionFind::unite(int x, int y) {
  // xとyの親
  x = find(x);
  y = find(y);
  if(x == y) return;

  // yのほうが深さが深い　xの親はyの親
  if(rank[x] < rank[y]) {
    par[x] = y;
    s[y] = s[x] + s[y];
  }
  else {
    par[y] = x;
    s[x] = s[x] + s[y];
    if( rank[x] == rank[y] ) rank[x]++;
  }
}

// xの属する連結成分のサイズ
int UnionFind::size(int x) { return s[find(x)];}

// xとyが同じ集合に属するか
bool UnionFind::same(int x, int y) { return find(x) == find(y);}

// 連結成分数
int UnionFind::group(int n) {
  REP(i, n) used[find(i)] = true;
  int ret = 0;
  REP(i, n) if(used[i]) ret++;
  return ret;
}

UnionFind uf;

int l[100010], r[100010], a[100010], b[100010], su[100010];
signed main(void)
{
  string s;
  cin >> s;
  int n;
  cin >> n;
  REP(i, n) cin >> l[i] >> r[i];

  REP(i, s.size()) a[i+1] = s[i]-'a';
  a[s.size()+1] = 0;
  REP(i, s.size()+1) b[i] = a[i+1] - a[i];

  REP(i, n) uf.unite(l[i]-1, r[i]);
  REP(i, (s.size()+1)/2) uf.unite(i, s.size()-i);

  REP(i, s.size()+1) {
    su[uf.find(i)] += b[i];
  }

  REP(i, s.size()+1) {
    if(su[uf.find(i)]%26 != 0) {
      cout << "NO" << endl;
      return 0;
    }
  }

  cout << "YES" << endl;

  return 0;
}