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;
struct O
{
	int l,r,x;
}b[200005];
int x,y,t,n,m,e[100005],a[100005]; 
char S[100005];
void add(int &u,int v)
{
	if (!v) return;
	if (!u) {u=v; return;}
	if (b[u].x<b[v].x)
	{
		add(b[u].r,v);
		swap(b[u].l,b[u].r);
	}
	else
	{
		add(b[v].r,u);
		swap(b[v].l,b[v].r);
		u=v;
	}
}
int main()
{
	scanf("%s",S+1); n=strlen(S+1);
	for (int i=1;i<=n;++i) a[i]+=S[i]-'a',a[i+1]-=S[i]-'a';
	scanf("%d",&m);
	for (int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		b[++t].x=y;
		add(e[x],t);
	}
	for (int i=1;i<=n+1>>1;++i)
	{
		b[++t].x=n-i+1;
		add(e[i],t);
	}
	for (int i=1;i<=n;++i)
	{
		a[i]%=26;
		while (e[i]&&b[e[i]].x<i) add(b[e[i]].l,b[e[i]].r),e[i]=b[e[i]].l;
		if (!e[i]){
			if (a[i]) {puts("NO"); return 0;}
			continue;
		}
		t=b[e[i]].x;
		a[t+1]+=a[i]; a[i]=0;
		add(e[t+1],b[e[i]].l);
		add(e[t+1],b[e[i]].r);
	}
	puts("YES");
	return 0;
}