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;
const int N=100005;
int f[N],x,y,m,v[N],fa[N],sum[N];
char s[N];
int find(int x){
	if (x==fa[x])return x;
	return fa[x]=find(fa[x]);
}
void link(int x,int y){
	x=find(x);y=find(y);
	if (x!=y)fa[x]=y;
}
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	for (int i=1;i<=n;i++)f[i]=s[i]-'a',fa[i]=i;
	n++;fa[n]=n;
	for (int i=n;i>1;i--)(f[i]+=26-f[i-1])%=26;
	for (int i=1,j=n;i<j;i++,j--)link(i,j);
	scanf("%d",&m);
	while (m--){
		scanf("%d%d",&x,&y);
		link(x,y+1);
	}
	for (int i=1;i<=n+1;i++)(sum[find(i)]+=f[i])%=26;
	for (int i=1;i<=n+1;i++)
		if (sum[i]){
			puts("NO");
			return 0;
		}
	puts("YES");
}