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 bool boolean;

const int N = 1e5 + 5;

int n, m;
int a[N];
char s[N];

int uf[N];
int find(int x) {
	return uf[x] == x ? x : (uf[x] = find(uf[x]));
}
void unit(int x, int y) {
	x = find(x), y = find(y);
	if (x ^ y) {
		uf[x] = y;
		a[y] += a[x];
	}
}

int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	scanf("%d", &m);
	for (int i = 1; i <= n; i++) {
		a[i] = s[i] - 'a';
	}
	for (int i = 1; i <= n + 1; i++) {
		uf[i] = i;
	}
	for (int i = n + 1; i; i--) {
		a[i] -= a[i - 1];
	}
	for (int l = 1, r = n; l + 1 < r; l++, r--) {
		unit(l + 1, r);		
	}
	for (int i = 1, l, r; i <= m; i++) {
		scanf("%d%d", &l, &r);
		unit(l, ++r);
	}
	for (int i = 2; i <= n; i++) {
		if (find(i) == i && (a[i] % 26) && find(i) != find(1) && find(i) != find(n + 1)) {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}