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>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 100005;

int n, m, a[MAXN], b[MAXN], f[MAXN];
char s[MAXN];

inline int Find(int x)
{
	while (x ^ f[x])
		x = f[x] = f[f[x]];
	return x;
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	scanf("%s", s + 1), n = strlen(s + 1), m = Read();
	for (int i = 1; i <= n; i ++)
		a[i] = s[i] - 'a';
	for (int i = n + 1; i; i --)
		f[i] = i, a[i] = (a[i] - a[i - 1] + 26) % 26;
	for (int i = 1, l, r; i <= m; i ++)
		l = Read(), r = Read(), f[Find(l)] = Find(r + 1);
	for (int i = 1; i <= n + 1; i ++)
		f[Find(i)] = Find(n + 2 - i);
	for (int i = 1; i <= n + 1; i ++)
		b[Find(i)] = (b[Find(i)] + a[i]) % 26;
	for (int i = 1; i <= n + 1; i ++)
		if (Find(i) == i && b[i])
			return puts("NO"), 0;
	return puts("YES"), 0;
}