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>
#include <set>
#include <algorithm>
#include <utility>

using namespace std;
using pii = pair<int, int>;

int main(){
	ios_base::sync_with_stdio(false);
	string s;
	cin >> s;
	const int n = s.size();
	int m;
	cin >> m;
	set<pii> ranges;
	for(int i = 0; i < m; ++i){
		int l, r;
		cin >> l >> r;
		--l;
		if(l >= (n + 1) / 2){
			const int t = l;
			l = n - r;
			r = n - t;
		}
		if(r > n / 2){ r = n - r; }
		if(r < l){ swap(l, r); }
		//cout << ">> " << l << " " << r << endl;
		if(l < r){ ranges.emplace(l, r); }
	}
	vector<int> a(n / 2);
	for(int i = 0; i < n / 2; ++i){
		a[i] = ((s[n - 1 - i] - 'a') - (s[i] - 'a') + 26) % 26;
	}
	vector<int> d(n / 2 + 1);
	bool answer = true;
	for(int i = 0, acc = 0; i < n / 2; ++i){
		vector<int> tails;
		while(!ranges.empty() && ranges.begin()->first == i){
			tails.push_back(ranges.begin()->second);
			ranges.erase(ranges.begin());
		}
		for(int j = 0; j + 1 < tails.size(); ++j){
			ranges.emplace(tails[j], tails[j + 1]);
		}
		acc = (acc - d[i] + 26) % 26;
		//cout << "i = " << i << ": " << acc << std::endl;
		if(tails.empty()){
			if(a[i] != acc){ answer = false; }
		}else{
			const int t = (a[i] - acc + 26) % 26;
			//cout << "? " << i << " - " << tails[0] << " => " << t << endl;
			d[tails[0]] = (d[tails[0]] + t) % 26;
			acc = (acc + t) % 26;
		}
	}
	cout << (answer ? "YES" : "NO") << endl;
	return 0;
}