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>
using namespace std;

struct UF {
	int par[100001];
	UF() { for (int i = 0; i < 100001; i++) par[i] = i; }
	int root(int x) { if (par[x] == x) return x; return par[x] = root(par[x]); }
	void marge(int x, int y) { par[root(x)] = root(y); }
};

string s;
int a[100001];
int n, l, r;
UF uf;
int Sum[100001];

int main() {
	int i;
	
	cin >> s;
	
	a[0] = s[0] - 'a';
	for (i = 0; i < (int)s.length() - 1; i++) {
		a[i + 1] = s[i + 1] - s[i];
		if (a[i + 1] < 0) a[i + 1] += 26;
	}
	a[s.length()] = 'a' - s[s.length() - 1] + 26;
	
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> l >> r;
		uf.marge(l - 1, r);
	}
	for (i = 0; i <= s.length(); i++) {
		uf.marge(i, s.length() - i);
	}
	
	for (i = 0; i <= s.length(); i++) {
		//cout << "i = " << i << " " << uf.par[i] << " " << a[i] << endl;
		Sum[uf.par[i]] += a[i];
		Sum[uf.par[i]] %= 26;
	}
	
	for (i = 0; i <= s.length(); i++) {
		if (Sum[i] != 0) {
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	return 0;
}