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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXLEN = 100000;
const int MAXN = 100000;

char s[MAXLEN + 1]; int len;
int n;
int l[MAXN], r[MAXN];

set<int> opt[MAXLEN + 1];
int optid[MAXLEN + 1];
int sub[MAXLEN + 1];

int merge(int a, int b) {
	if (SZ(opt[a]) < SZ(opt[b])) swap(a, b);
	for (auto it = opt[b].begin(); it != opt[b].end(); ++it) opt[a].insert(*it);
	return a;
}

bool solve() {
	int hlen = len / 2;
	REPE(i, len) optid[i] = i, sub[i] = 0;
	REP(i, n) {
		if (len - r[i] - 1 == l[i]) continue;
		if (l[i] > len - l[i] - 1) l[i] = len - l[i] - 1, r[i] = len - r[i] - 1, swap(l[i], r[i]);
		else if (r[i] >= len - r[i] - 1 && l[i] < len - r[i] - 1) r[i] = len - r[i] - 1 - 1;
		else if (r[i] >= len - r[i] - 1) l[i] = l[i] - 1, r[i] = len - r[i] - 1, swap(l[i], r[i]);
		opt[l[i]].insert(r[i] + 1);
		//printf("%d: %d..%d\n", i, l[i], r[i]);
	}
	//REPE(i, len) { printf("%d:", i); for (auto it = opt[i].begin(); it != opt[i].end(); ++it) printf(" %d", *it); puts(""); }

	int cnt = 0;
	REP(i, hlen) {
		int x = (s[i] - 'a' + cnt) % 26, y = s[len - i - 1] - 'a', need = (y - x + 26) % 26;
		if (SZ(opt[optid[i]]) == 0) {
			if (need != 0) return false;
		} else {
			auto it = opt[optid[i]].begin(); int cr = *it; opt[optid[i]].erase(it);
			cnt += need; sub[cr] += need;
			optid[cr] = merge(optid[i], optid[cr]);
		}
		cnt = ((cnt - sub[i + 1]) % 26 + 26) % 26;
	}
	assert(cnt == 0);
	return true;
}

void run() {
	scanf("%s", s); len = strlen(s);
	scanf("%d", &n); REP(i, n) scanf("%d%d", &l[i], &r[i]), --l[i], --r[i];

	printf("%s\n", solve() ? "YES" : "NO");
}

int main() {
	run();
	return 0;
}