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;
const int N = 1e5 + 5;
char s[N], rs[N];
set<int> sls[N];
vector<int> sl[N];
int a[N];
void my_merge(set<int> &a, set<int> &b) {
	if (b.size() < a.size()) {
		for (int i : b) a.insert(i);
	}
	else {
		for (int i : a) b.insert(i);
		a.swap(b);
	}
}
int main() {
	scanf("%s", s);
	int m = (int) strlen(s);
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; ++ i) {
		int l, r;
		scanf("%d%d", &l, &r); -- l, -- r;
		if (l <= (m - 1) / 2 && r >= m / 2) {
			int dl = (m - 1) / 2 - l;
			int dr = r - m / 2;
			if (dl == dr) continue;
			if (dl < dr) {
				l = m / 2 + dl + 1;
			}
			else {
				r = (m - 1) / 2 - dr - 1;
			}
			assert(l <= r && (r <= (m - 1) / 2 || l >= m / 2));
		}
		if (r <= (m - 1) / 2) {
			sls[l].insert(r);
		}
		else {
			sls[m - 1 - r].insert(m - 1 - l);
		}
	}
	for (int i = 0; i <= (m - 1) / 2; ++ i) {
		//sort(sl[i].begin(), sl[i].end());
		while (sls[i].size() && *(sls[i].begin()) < i) {
			sls[i].erase(sls[i].begin());
		}
		if (sls[i].size()) {
			sl[i].push_back(*(sls[i].begin()));
			my_merge(sls[sl[i].back() + 1], sls[i]);
		}
	}
	for (int i = 0; i < m; ++ i) rs[m - i - 1] = s[i];
	int res = 0, gg = 0;
	for (int i = 0; i <= (m - 1) / 2; ++ i) {
		res += a[i];
		s[i] = (s[i] - 'a' + res) % 26 + 'a';
		if (sl[i].size()) {
			int delta = (26 + (rs[i] - 'a') - (s[i] - 'a')) % 26;
			s[i] = (s[i] - 'a' + delta) % 26 + 'a';
			assert(s[i] == rs[i]);
			res += delta;
			a[sl[i][0] + 1] -= delta;
		}
		if (s[i] != rs[i]) { gg = 1; break; }
	}
	puts(gg ? "NO" : "YES");
}