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 <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

class UnionFind {
public:
  vector<int> par, rank;
  // if par is negative, it is a root, of which tree size is the abs-value.
  // rank represents depth
  UnionFind(int sz) : par(sz, -1), rank(sz, 0){}
  int find(int x){
    if(par[x]<0) return x;
    else return par[x] = find(par[x]);
  }
  void unite(int x, int y){
    x=find(x); y=find(y);
    if(x==y) return;
    if(rank[x] < rank[y]) swap(x,y);
    par[x] += par[y];
    par[y] = x;
    if(rank[x]==rank[y]) rank[x]++;
  }
  inline bool same(int x, int y){ return find(x) == find(y); }
  inline int size(int x){ return -par[find(x)]; }
};


bool solve(){
  string s;
  int q;
  cin>>s>>q;
  int n = s.size();
  vector<int> l(q),r(q);
  rep(i,q) cin>>l[i]>>r[i];

  if(n==1) return true;

  rep(i,q){
    l[i]--;
    if(l[i]<n/2 && (n+1)/2<r[i]){
      if(l[i] < n-r[i]){
        r[i] = n-r[i];
      }
      else if(n-r[i] < l[i]){
        swap(l[i], r[i]);
        l[i] = n - l[i];
      }
      else {
        // to ignore this
        l[i] = (n+1)/2;
        r[i] = (n+1)/2;
      }
    }
    else if(n/2<=l[i]){
      swap(l[i],r[i]);
      l[i] = n-l[i];
      r[i] = n-r[i];
    }
  }

  UnionFind uf(q);

  map<int,int> pos;
  // positions -> idx
  rep(i,q){
    if(pos.count(l[i])){
      uf.unite(i, pos[l[i]]);
    } else {
      pos[l[i]] = i;
    }
    if(pos.count(r[i])){
      uf.unite(i, pos[r[i]]);
    } else {
      pos[r[i]] = i;
    }
  }

  // build range group
  map<int,vector<int>> gp;
  rep(i,q){
    gp[uf.find(i)].pb(l[i]);
    gp[uf.find(i)].pb(r[i]);
  }

  vector<int> ranges(n/2+1, -1); // begin -> end
  for(auto &&pv : gp){
    auto &&v = pv.second;
    if(v.size()){
      uniq(v);
      rep(i,v.size()-1){
        ranges[v[i]] = v[i+1];
      }
    }
  }

  int crnt = 0;
  vector<int> memo(n/2+1, 0);
  rep(i,n/2){
    int req = (s[n-i-1] - s[i] + 26)%26;
    crnt = (crnt + memo[i]) % 26;
    if(crnt != req){
      if(ranges[i] == -1) return false;
      int add = (req + 26 - crnt)%26;
      memo[ranges[i]] = 26-add;
      crnt = (crnt + add) % 26;
    }
    assert(crnt == req);
  }

  return true;
}

int main(){
  if(solve()) cout << "YES" << endl;
  else cout << "NO" << endl;

  return 0;
}