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

string S; int Q, l[100009], r[100009], a[100009], b[100009], col[100009], cntw; bool used[100009], flag;
vector<pair<int, int>>D; vector<int>X[100009], V[100009];

int dfs(int pos) {
	int sum = 0; used[pos] = true;
	for (int i = 0; i < X[pos].size(); i++) {
		if (used[X[pos][i]] == true) continue;
		sum += dfs(X[pos][i]); sum %= 26;
	}
	return (sum - b[pos] + 26) % 26;
}
void dfs2(int pos) {
	if (col[pos] >= 1) return;
	col[pos] = cntw; V[cntw].push_back(pos);
	for (int i = 0; i < X[pos].size(); i++) dfs2(X[pos][i]);
}

int main() {
	cin >> S;
	for (int i = 0; i < S.size() / 2; i++) { a[i + 1] = (S[i] - S[S.size() - i - 1]); if (a[i + 1] < 0)a[i + 1] += 26; }
	for (int i = 0; i < (S.size() / 2) + 1; i++) { b[i] = (a[i + 1] - a[i] + 26) % 26; }
	cin >> Q;
	for (int i = 1; i <= Q; i++) {
		cin >> l[i] >> r[i]; l[i]--; r[i]--;
		if (l[i] + r[i] == S.size() - 1) continue;
		if (l[i] + r[i] >= S.size() - 1) {
			l[i] = S.size() - 1 - l[i];
			r[i] = S.size() - 1 - r[i];
			swap(l[i], r[i]);
		}
		int P1 = l[i], P2 = r[i];
		if (r[i] >= S.size() / 2) P2 = S.size() - 2 - r[i];
		D.push_back(make_pair(P1 + 1, P2 + 1));
	}
	for (int i = 0; i < D.size(); i++) {
		X[D[i].first - 1].push_back(D[i].second);
		X[D[i].second].push_back(D[i].first - 1);
	}
	for (int i = 0; i < (S.size() / 2) + 1; i++) {
		if (col[i] >= 1) continue;
		cntw++; dfs2(i);
	}
	for (int i = 1; i <= cntw; i++) {
		int U = dfs(V[i][0]);
		if (U != 0) flag = true;
	}
	if (flag == true) cout << "NO" << endl;
	else cout << "YES" << endl;
	return 0;
}