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 <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
char s[SZ]; int n,m,l[SZ],r[SZ],g[SZ],rs[SZ];
set<pii> ss;
int ch[SZ][2],dis[SZ],v[SZ],an=0;
int merge(int a,int b)
{
    if(!a||!b) return a+b;
    if(v[a]>v[b]) swap(a,b);
    ch[a][1]=merge(ch[a][1],b);
    if(dis[ch[a][0]]<dis[ch[a][1]]) swap(ch[a][0],ch[a][1]);
    if(!ch[a][1]) dis[a]=0;
    else dis[a]=dis[ch[a][1]]+1;
    return a;
}
int pop(int a)
{
    int t=merge(ch[a][0],ch[a][1]);
    ch[a][0]=ch[a][1]=dis[a]=0;
    return t;
}
int R[SZ];
int bb[SZ];
void edt(int x,int y)
{
	for(;x<=SZ;x+=x&-x) (bb[x]+=y)%=26;
}
int qry(int x)
{
	int s=0;
	for(;x>=1;x-=x&-x) (s+=bb[x])%=26;
	return s;
}
void add(int l,int r,int v)
{
	edt(l,v); edt(r+1,(26-v)%26);
}
int main()
{
	scanf("%s",s+1); n=strlen(s+1);
	scanf("%d",&m);
	int dv=n/2;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",l+i,r+i);
		if(l[i]>n+1-r[i]) l[i]=n+1-l[i],r[i]=n+1-r[i],swap(l[i],r[i]);
		if(r[i]>dv) r[i]=n-r[i];
		if(l[i]>r[i]) continue;
		++an; v[an]=r[i]; rs[l[i]]=merge(rs[l[i]],an);
	}
	for(int i=1;i<=dv;++i)
	{
		if(!rs[i]) continue;
		R[i]=v[rs[i]];
		while(rs[i]&&v[rs[i]]==R[i]) rs[i]=pop(rs[i]);
		rs[R[i]+1]=merge(rs[R[i]+1],rs[i]); rs[i]=0;
	}
	for(int i=1;i<=dv;++i)
	{
		g[i]=s[i]-s[n+1-i];
		while(g[i]<0) g[i]+=26;
		while(g[i]>=26) g[i]-=26;
		add(i,i,g[i]);
		int x=qry(i);
		if(R[i]) add(i,R[i],(26-x)%26);
	}
	for(int i=1;i<=dv;++i)
		if(qry(i)) {puts("NO");return 0;}
	puts("YES");
}