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;
using Int = long long;

struct UnionFind{
  Int n;
  vector<Int> r,p;
  UnionFind(){}
  UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);}
  Int find(Int x){
    return (x==p[x]?x:p[x]=find(p[x]));
  }
  bool same(Int x,Int y){
    return find(x)==find(y);
  }
  void unite(Int x,Int y){
    x=find(x);y=find(y);
    if(x==y) return;
    if(r[x]<r[y]) swap(x,y);
    r[x]+=r[y];
    p[y]=x;
  }
};

//INSERT ABOVE HERE
signed main(){
  string s;
  cin>>s;
  s="a"+s+"a";

  UnionFind uf(s.size()-1);
  vector<Int> v(s.size()-1);
  for(Int i=0;i<(Int)s.size()-1;i++) v[i]=s[i]-s[i+1]+26;
  
  Int n;
  cin>>n;
  for(Int i=0;i<n;i++){
    Int l,r;
    cin>>l>>r;
    l--;
    uf.unite(l,r);
  }

  for(Int i=0;i<(Int)s.size()-1-(1+i);i++)
    uf.unite(i,(Int)s.size()-1-(1+i));

  vector<Int> ans(s.size()-1,0);
  for(Int i=0;i<(Int)s.size()-1;i++)
    ans[uf.find(i)]+=v[i];

  //for(Int x:ans) cout<<x<<endl;

  Int flg=0;
  for(Int x:ans) flg|=x%26;

  cout<<(flg?"NO":"YES")<<endl;
  return 0;
}