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 <string>
#include <map>
#include <vector>

using namespace std;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

string s;
int a[100005];
int n;
int l[100005], r[100005];
int dif[100005];
UnionFind uf(100005);
map<int, int> mp;

int main(void)
{
	cin >> s;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
	
	for(int i = 0; i < s.size(); i++){
		a[i+1] = (int)(s[i] - 'a');
	}
	int N = s.size() + 1;
	
	for(int i = 1; i <= N; i++){
		dif[i] = (a[i] - a[i-1] + 26) % 26;
	}
	for(int i = 1; i <= N; i++) uf.unite(i, N-i+1);
	for(int i = 1; i <= n; i++) uf.unite(l[i], r[i]+1);
	
	for(int i = 1; i <= N; i++){
		mp[uf.root(i)] += dif[i];
	}
	for(auto it = mp.begin(); it != mp.end(); it++){
		if(it->second % 26){
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	
	return 0;
}