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<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<functional>
using namespace std;
#define ran 111111
int N;
char s[ran];
int todo[ran];
typedef priority_queue<int,vector<int>,greater<int> > ves;
ves *q[ran];
ves Q[ran];

int val[ran * 4];
void build(int i,int s,int e){
	if(s==e){
		val[i] = todo[s];
		return;
	}
	int m = (s+e)/2;
	build(i*2,s,m);
	build(i*2+1,m+1,e);
}
void pus(int i){
	int&tmp = val[i];
	val[i*2] = (val[i*2] + tmp)%26;
	val[i*2+1] = (val[i*2+1] + tmp)%26;
	tmp = 0;
}
void inc(int i,int s,int e,int l,int r,int x){
	if(s == l && e == r){
		val[i] = (val[i] + x)%26;
		return;
	}
	pus(i);
	int m=(s+e)/2;
	if(r <= m)inc(i*2,s,m,l,r,x);else
		if(l>m)inc(i*2+1,m+1,e,l,r,x);else{
			inc(i*2,s,m,l,m,x);
			inc(i*2+1,m+1,e,m+1,r,x);
		}
}
int query(int i,int s,int e,int x){
	if(s == e)return val[i];
	pus(i);
	int m=(s+e)/2;
	if(x<=m)return query(i*2,s,m,x);
	return query(i*2+1,m+1,e,x);
}

void merge(ves*big,ves*small){
	while(!small->empty()){
		int x = small->top();
		small->pop();
		big->push(x);
	}
}

int main(){
	scanf("%s",s+1);
	int n = strlen(s+1), m;
	N = n/2;
	for(int i=1, j=n; i<=N; i++,j--){
		todo[i] = (s[j] - s[i] + 26)%26;
		q[i] = &Q[i];
	}
	build(1,1,N);
	for(scanf("%d",&m); m--;){
		int st, en;
		scanf("%d%d",&st,&en);
		if(en > N){
			if(st > N){
				st = n+1 - st;
				en = n+1 - en;
				swap(st, en);
			}else{
				en = n+1 - en;
				if(st > en)swap(st, en);
				--en;
			}
		}
		if(en > N)--en;
		if(st > en)continue;
		q[st]->push(en);
	}
	for(int i=1; i<=N; i++){
		int xx = query(1,1,N,i);
		if(q[i]->empty()){
			if(xx != 0){
				puts("NO");
				return 0;
			}
			continue;
		}
		int tt = q[i]->top();
		inc(1,1,N,i,tt,26-xx);
		while(!q[i]->empty() && q[i]->top() == tt)
			q[i]->pop();
		if(tt + 1 > N)continue;
		if(q[i]->size() > q[tt+1]->size()){
			merge(q[i], q[tt+1]);
			q[tt+1] = q[i];
		}else{
			merge(q[tt+1],q[i]);
		}
	}
	puts("YES");
	return 0;
}