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 sqr(x) ((x)*(x))
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define vi vector<int>
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > 
#define pii pair<int,int> 
#define pb push_back
#define mp make_pair
#define debuge cerr<<"isok"<<endl
#define debug(x) cerr<<#x<<"="<<x<<endl
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
#define SS second
#define FF first
#define ls (k<<1)
#define rs (k<<1|1)
#define clr(a,x) memset(a,x,sizeof(a))
#define cpy(a,x) memcpy(a,x,sizeof(a))
#define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define SZ(x) ((int)x.size())
using namespace std;
template<class T> inline void gmin(T &x,const T &y){if(x>y) x=y;}
template<class T> inline void gmax(T &x,const T &y){if(x<y) x=y;}
const int BufferSize=1<<16;
char buffer[BufferSize],*Bufferhead,*Buffertail;
bool Terminal;
inline char Getchar(){
	if(Bufferhead==Buffertail){
		int l=fread(buffer,1,BufferSize,stdin);
		if(!l){Terminal=1;return 0;}
		Buffertail=(Bufferhead=buffer)+l;
	}
	return *Bufferhead++;
}
template<class T>inline bool read(T &x){
	x=0;char c=Getchar(),rev=0;
	while(c<'0'||c>'9'){rev|=c=='-';c=Getchar();if(Terminal)return 0;}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=Getchar();
	if(c=='.'){
		c=Getchar();double t=0.1;
		while(c>='0'&&c<='9') x=x+(c-'0')*t,c=Getchar(),t=t/10;
	}
	x=rev?-x:x;
	return 1;
}
template<class T1,class T2> inline bool read(T1 &x,T2 &y){return read(x)&read(y);}
template<class T1,class T2,class T3> inline bool read(T1 &x,T2 &y,T3 &z){return read(x)&read(y)&read(z);}
template<class T1,class T2,class T3,class T4> inline bool read(T1 &x,T2 &y,T3 &z,T4 &w){return read(x)&read(y)&read(z)&read(w);}
inline bool reads(char *x){
	char c=Getchar();
	while(c<33||c>126){c=Getchar();if(Terminal)return 0;}
	while(c>=33&&c<=126) (*x++)=c,c=Getchar();
	*x=0;return 1;
}
template<class T>inline void print(T x,const char c='\n'){
	if(!x){putchar('0');putchar(c);return;}
	if(x<0) putchar('-'),x=-x;
	int m=0,a[20];
	while(x) a[m++]=x%10,x/=10;
	while(m--) putchar(a[m]+'0');
	putchar(c);
}
//--------------------------------head---------------------------------------------

const int inf=0x3f3f3f3f;
const int N=200005,M=100005,mod=26;
template<class T,class S> inline void ch(T &x,const S y){x=(x+y)%mod;}
inline int exp(int x,int y,const int mod=::mod){
	int ans=1;
	while(y){
		if(y&1) ans=(ll)ans*x%mod;
		x=(ll)x*x%mod;y>>=1;
	}return ans;
}

int n,m,h,root[N],a[N],x[N],lc[N],rc[N],len[N],c[N];
char s[N];

inline void add(int x,int y){while(x<=h) ch(c[x],y),x+=x&-x;}
inline void add(int l,int r,int y){add(l,y);add(r+1,mod-y);}
inline int get(int x){int ans=0;while(x) ch(ans,c[x]),x-=x&-x;return ans;}
inline int merge(int x,int y){
	if(!x||!y) return x|y;
	if(a[x]>a[y]) swap(x,y);
	rc[x]=merge(rc[x],y);
	if(len[lc[x]]<len[rc[x]]) swap(lc[x],rc[x]);
	len[x]=len[rc[x]]+1;
	return x;
}
inline void pop(int &x){x=merge(lc[x],rc[x]);}

int main(){
#ifdef rqgao2014
	assert(freopen("input.txt","r",stdin));
#endif
	scanf("%s",s+1);n=strlen(s+1);
	scanf("%d",&m);
	h=(n+1)/2;
	for(int i=1;i<=h;i++)
		x[i]=(s[n-i+1]-s[i]+mod)%mod;
	for(int i=1;i<=h;i++)
		add(i,(x[i]-x[i-1]+mod)%mod);
	for(int i=1;i<=m;i++){
		int l,r;scanf("%d%d",&l,&r);
		if(r<=h) r-=(r==n/2+1);
		else if(l>h) l=n-l+1,r=n-r+1,swap(l,r); 
		else{
			r=n-r+1;
			if(l>r) swap(l,r);
			r--;
		}
		if(l>r) continue;
		a[i]=r;
		root[l]=merge(root[l],i);
		dprintf("%d %d\n",l,r);
	}
//	for(int i=1;i<=h;i++) dprintf("%d ",x[i]);dprintf("\n");
	for(int i=1;i<=h;i++){
		while(root[i]&&a[root[i]]<i)
			pop(root[i]);
		if(root[i]){
			int r=a[root[i]];
			pop(root[i]);
//			dprintf("%d %d %d\n",i,r,get(i));
			add(i,r,mod-get(i));
			root[r+1]=merge(root[i],root[r+1]);
		}
//		debug(get(3));
		if(get(i)){puts("NO");return 0;}
	}
	puts("YES");
	return 0;
}