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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<unordered_map>
#include<array>
#include<map>
#include<bitset>
#include<iomanip>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define dme cout<<"IMPOSSIBLE"<<endl;return 0
//ios::sync_with_stdio(false);
//std::cin.tie(0);
//<< setprecision(20)
//19234567892927;
const int mod=1e9+7;
const llint big=1e13+100;
const long double pai=3.141592653589793238462643383279502884197;
const long double ena=2.71828182845904523536;
const long double eps=1e-7;
template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}}
template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){return a/gcd(a,b)*b;}
//順番??関係ないね
int main(void){
	int i,j,n,m;
	string str;cin>>str;
	m=str.size();
	vector<int>sa(m/2);
	vector<int>imsa(m/2+1);
	cin>>n;
	for(i=0;i<m/2;i++){sa[i]=str[i]-str[m-i-1];}//これを0にする
	for(i=1;i<m/2;i++){imsa[i]=sa[i]-sa[i-1];}
	imsa[m/2]=-sa[m/2-1];
	imsa[0]=sa[0];
	//imsaを0にする
	//for(auto it:imsa){cerr<<"imsa"<<it<<endl;}
	vector<int> oya(m/2+1);
	vector<int> ran(m/2+1);
	for(i=0;i<oya.size();i++){oya[i]=i;}
	for(i=0;i<n;i++){
		int l,r;cin>>l>>r;
		l=min(l-1,m-(l-1));
		r=min(r,m-r);
		//cerr<<"de l,r="<<l<<" "<<r<<endl;
		//lとrを津図ける
		while(l!=oya[l]){l=oya[l];}
		while(r!=oya[r]){r=oya[r];}
		if(l==r){continue;}
		if(ran[l]<ran[r]){swap(l,r);}
		oya[r]=l;
		if(ran[l]==ran[r]){ran[l]++;}
	}
	vector<int>go(m/2+1,-1);//次の頂点
	vector<int>mae(m/2+1,-1);//それにおとずれたもの
	for(i=0;i<oya.size();i++){
		int gen=i;
		while(gen!=oya[gen]){gen=oya[gen];}
		if(mae[gen]!=-1){go[mae[gen]]=i;}
		mae[gen]=i;
	}
	//imsaをすべて0にしよう
	for(i=0;i<imsa.size();i++){
		if(go[i]==-1&&imsa[i]%26!=0){cout<<"NO"<<endl;return 0;}
		if(go[i]!=-1){imsa[go[i]]+=imsa[i];}
	}
	cout<<"YES"<<endl;
	return 0;
}