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>
#define maxn 1000100
using namespace std;
int n,sum[maxn*2],tp,m,a[maxn],f[maxn];
char s[maxn];
int g(int x){
	return x<0?x+26:x;
}
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
int main(){
	scanf("%s%d",s+1,&n);
	int m=strlen(s+1);
	for(int i=1;i<=m;++i)s[i]-='a',f[i]=i;
	f[m+1]=m+1;
	for(int i=m+1;i>=1;--i)s[i]=g(s[i]-s[i-1]);
	for(int i=1,l,r;i<=n;++i)
		scanf("%d%d",&l,&r),f[find(l)]=find(r+1);
	for(int i=1;i<=m-i+2;++i)f[find(i)]=find(m+2-i);
	for(int i=1;i<=m+1;++i)sum[find(i)]+=s[i];
	for(int i=1;i<=m+1;++i)if(i==find(i)&&sum[i]%26)return puts("NO"),0;
	puts("YES");
}