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;
typedef long long ll;
typedef pair<int,int> pp;
typedef pair<ll,ll> pll;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define eb emplace_back
#define x first
#define y second

char s[100010]; int m;
int n_, n;
pp dd[100010];
int targ[100010];

int par[100010];
int diff[100010];
int r(int x){ return (x==par[x])?x:(par[x]=r(par[x])); }

int main()
{
	scanf("%s", s+1); m = strlen(s+1);
	read(n_);
	for(int i=1; i<=n_; ++i){
		int l, r; read(l, r);
		if(m%2==1 && r == m/2+1) --r;
		if(m%2==1 && l == m/2+1) ++l;
		if(l>r) continue;
		if(l <= m/2){
			if(r <= m/2){
				dd[++n] = {m+1-r, m+1-l};
			} else {
				if(l+r == m+1) continue;
				if(l > m+1-r){
					l = m+2-l;
				} else {
					r = r+1;
					l = m+1-l;
					swap(l, r);
				}
				dd[++n] = {l, r};
			}
		} else {
			dd[++n] = {l, r};
		}
		//printf("Converted to: %d %d\n", dd[n].x, dd[n].y);
	}
	for(int i=m/2+2; i<=m; ++i){
		targ[i] = ((52 + s[m+1-i]) - s[m+2-i]) % 26;
	}
	int from = (m+1)/2+1;
	//for(int i=from; i<=m; ++i) printf("targ[%c] = %d\n", s[i], targ[i]);
	for(int i=from; i<=m+1; ++i) par[i]=i, diff[i]=((targ[i]+52)-(s[i]-s[i-1])) % 26;
	for(int i=1; i<=n; ++i){
		int a, b; tie(a, b) = dd[i]; ++b;
		a=r(a); b=r(b);
		if(a!=b){
			diff[b] += diff[a];
			par[a] = b;
		}
	}
	for(int i=from; i<=m+1; ++i) if(par[i] == i){
		if(diff[i]%26 && r(m+1)!=i){
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}