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<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;

const int N=100005;

int n,l,r,m,ans;
int a[N],vis[N];
char s[N];
vector<int> lev[N];

void dfs(int k){
	int u,j; ans+=a[k];
	vis[k]=1;
	for (j=0;j<lev[k].size();j++){
		u=lev[k][j];
		if (vis[u]) continue;
		dfs(u);
	}
}

int main(){
	int i;
	scanf("%s",s+1); n=strlen(s+1);
	scanf("%d",&m);
	for (i=1;i<=m;i++){
		scanf("%d%d",&l,&r);
		lev[l-1].push_back(r);
		lev[r].push_back(l-1);
	}
	s[0]=s[n+1]='a';
	for (i=0;i<=n;i++) a[i]=((s[i+1]-s[i])%26+26)%26;
	for (i=0;i<=n;i++) lev[i].push_back(n-i);
	for (i=0;i<=n;i++)
		if (!vis[i]){
			ans=0;
			dfs(i);
			if (ans%26!=0){
				printf("NO\n");
				return 0;
			}
		}
	printf("YES\n");
	return 0;
}