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>
typedef long long ll;
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

using namespace std;
string rawS;
vector<int> S;
const int MAX_N=1e5,ALP='z'-'a'+1,MAX_M=1e5;
typedef pair<int,int> P;
int N,M;
int L[MAX_N],R[MAX_N],dif[MAX_M+1];
bool used[MAX_M+1];
vector<int> G[MAX_M+1];
int dfs(int v){
	used[v]=true;
	int ret=dif[v];
	for(auto e:G[v]){
		if(!used[e]){
			ret+=dfs(e);
			ret%=ALP;
		}
	}
	return ret;
}
int main(){
	cin>>rawS>>N;
	M=(int)rawS.size();
	bool ans;
	REP(i,M){
		S.push_back(rawS[i]-'a');
	}
	REP(i,N)cin>>L[i]>>R[i];
	REP(i,N){
		L[i]--;
		G[L[i]].push_back(R[i]);
		G[R[i]].push_back(L[i]);
	}
	REP(i,(M+1)/2){
		G[i].push_back(M-i);
		G[M-i].push_back(i);
	}
	REP(i,M+1){
		int a,b;
		a=(i<M ? S[i] : 0);
		b=(i-1>=0 ? S[i-1]:0);
		dif[i]=a-b;
		dif[i]+=ALP;
		dif[i]%=ALP;
	}
	ans=true;
	REP(i,M+1){
		if(!used[i]){
			if(dfs(i)>0){
				ans=false;
			}
		}
	}
	
	cout<<(ans ? "YES" : "NO")<<endl;
}