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<LL,LL> PII;

class UF{
public:
	vector<int> parent;
	UF(int N){
		parent.resize(N);
		for(int i=0; i<N; i++)
			parent[i] = i;
	}
	int find(int v) {
		if(v == parent[v]) return v;
		return parent[v] = find(parent[v]);
	}
	
	void uni(int u, int v) {
		u = find(u);
		v = find(v);
		parent[v] = u;
		
	}
	
	vector<int> fin() {
		int N = parent.size();
		vector<int> ret(N, -1);
		vector<int> prev(N, -1);
		for(int i=0; i<N; i++) {
			int pos = find(i);
			if(prev[pos] != -1) {
				ret[prev[pos]] = i;
			}
			prev[pos] = i;
			
		}
		return ret;
	}
	
	
	
};



int main() {
	string s;
	cin >> s;
	int M;
	cin >> M;
	int N = s.size();
	vector<int> diff(N, 0);
	for(int i=0; i<N/2; i++) {
		diff[i] = (s[N-1-i] - s[i]);
		diff[i] += 26*5;
		diff[i] %= 26;
	}
	
//	priority_queue<PII, vector<PII>, greater<PII> > Q;
//	vector<PII> Q;
	UF uf(N);
	for(int i=0; i<M; i++) {
		int l,r;
		cin >> l >> r;
		l--; r--;
		if(N-r-1 <= l) {
			int ll = l;
			l = N-1-r;
			r = N-1-ll;
		}
//		cout << l << " " << r << endl;
		if(r >= N/2) r = N-1-r-1;
		//assert(l <= r);
//		cout << l << " " << r+1 << endl;
		if(l <= r) {
			r++;
			//Q.push(PII(l,r));
			uf.uni(l, r);
		}
	}
	vector<int> next = uf.fin();
	
	/*
	for(int i=0; i<next.size(); i++)
		cout << next[i] << " ";
		
	cout << endl;
	*/
	for(int i=0; i<N/2; i++) {
	//cout << i << endl;
	/*
		for(int j=0; j<N; j++) {
			cout << diff[j] << " ";
		}
		cout << endl;
		*/
		int nx = next[i];
		if(nx == -1) continue;
		int adder = -diff[i];
		for(int j=i; j<nx; j++) {
			diff[j] += adder;
			diff[j] %= 26;
		}
		
	}
	for(int i=0; i<N/2; i++) {
		if(diff[i] != 0) {
			cout << "NO" << endl;
			return 0;
		}
	}
	
	cout << "YES" << endl;
	
	
	//vector<PII> res;
	
	
	
	
	
	/*
	PII prev = PII(-1, -1); 
	while(!Q.empty() ) {
		PII cur = Q.top(); Q.pop();
		if(cur.first == prev.first) {
			PII next = cur;
			next.first = prev.second+1l
			Q.push(cur.prev, );
		}
		
		
	}
	*/
	
	
	
	
	return 0;
}