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<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_set>
#include<unordered_map>
using namespace std;

#define MAX 100003

char buf[MAX];
int n;

string s;

vector<pair<int, int> > v;

vector<int> dif;
int belong[MAX];
int sum[MAX];

inline int root(int b) {
	if (belong[b] == -1) {
		return b;
	}
	belong[b] = root(belong[b]);
	return belong[b];
}
void merge(int a, int b) {
	a = root(a);
	b = root(b);
	if (a == b) {
		return;
	}
	belong[a] = b;
	sum[b] += sum[a];
	if (sum[b] >= 26)sum[b] -= 26;
}

int main() {
	memset(belong, -1, sizeof(belong));
	scanf("%s", buf);
	s = buf;
	cin >> n;
	s.insert(0, "a");
	s.push_back('a');
	for (int i = 0; i + 1 < s.size(); i++) {
		dif.push_back(26+(s[i + 1] - s[i]));
		dif.back() %= 26;
		sum[i] = dif.back();
	}
	for (int i = 0; i < n; i++) {
		int l, r;
		scanf("%d%d", &l, &r);
		l--;
		r--;
		merge(l, r + 1);
	}
	int rig = dif.size() - 1;
	for (int i = 0; i < dif.size(); i++) {
		merge(i, rig);
		rig--;
	}
	for (int i = 0; i < dif.size(); i++) {
		if (sum[root(i)] % 26 == 0) {

		}
		else {
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	return 0;
}