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 <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 100010

struct UF {
	int par[N],rank[N];
	
	void init(int n){
		for(int i = 0; i < n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}
	
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = par[x];
			if(rank[x] == rank[y]) rank[y]++;
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
};

string s;
int n, l[N], r[N], a[N], t[N], used[N];

int main(){
	cin>>s;
	n = s.size();
	ll kk = (n+1)/2;
	int m;
	cin>>m;
	rep(i, m){
		cin>>l[i]>>r[i];
		if(n%2==1){
			if(l[i]==kk);
			else if(l[i]>=kk) l[i]--;
			if(r[i]>=kk) r[i]--;
		}
		l[i]--; r[i]--;
	}
	if(n%2==1){
		s = s.substr(0, kk-1)+s.substr(kk);
		n--;
	}
	int n2 = n/2;
	rep(i, n2) a[i] = s[i]-s[n-i-1];
	for(ll i = n2-1; i >= 0; i--) t[i+1] = a[i+1]-a[i];
	t[0] = a[0];
	//rep(i, n2) cerr<<a[i]<<" "; cerr<<endl;
	//rep(i, n2+1) cerr<<t[i]<<" "; cerr<<endl;
	UF uf;
	uf.init(n2+1);
	rep(i, m){
		if(l[i]>r[i]) continue;
		if(r[i]<n2) continue;
		if(l[i]>=n2){
			ll r2 = 2*n2-l[i]-1;
			ll l2 = 2*n2-r[i]-1;
			l[i] = l2;
			r[i] = r2;
		} else {
			ll wl = n2-l[i];
			ll wr = r[i]-n2+1;
			if(wl==wr){
				l[i] = r[i] = -1;
			} else if(wl>wr){
				r[i] = l[i]+wl-wr-1;
			} else {
				r[i] = l[i]-1;
				l[i] = l[i] - (wr-wl);
			}
		}
	}
	rep(i, m){
		if(l[i]>r[i]) continue;
		if(l[i]<0) continue;
		uf.unite(l[i], r[i]+1);
		//cerr<<l[i]<<" "<<r[i]<<endl;
	}
	bool f = true;
	vector<vector<int> > v(n2+1);
	rep(i, n2+1) v[uf.find(i)].push_back(i);
	rep(i, n2+1){
		if(v[i].empty()) continue;
		ll x = 0;
		bool g = false;
		rep(j, v[i].size()){
			x += t[v[i][j]];
			//if(v[i][j]==n2) g = true;
		}
		if(!g && (x%26+26)%26!=0) f = false;
	}

	cout<<(f?"YES":"NO")<<endl;
	return 0;
}