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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <cstring>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <array>
#include <cassert>
#include <bitset>
using namespace std;
using LL = long long;

string S;
int N, M;
vector<pair<int, int>>vec;


//区間上のすべての要素に一様に値を加算するクエリも処理できるセグ木
//minでなければいけない
//いい感じに変えるとRUQ(区間上のすべての要素をある値に変更する)ができそう(適当)
template<typename T, typename Comp>
class RMQ_starry {
private:
	const T DEF;//デフォルト値(minではINF、sumでは0など)
	vector<T> seg;//生データ
	int width;//セグ木の幅(配列の大きさではない！)
	vector<T>lazy;//遅延データ(区間の加算)
				  //k番目のノード[l,r)の遅延伝播をする
	void eval(int k, int l, int r) {
		if (lazy[k] != 0) {
			seg[k] += lazy[k];
			if (r - l > 1) {
				lazy[2 * k + 1] += lazy[k];
				lazy[2 * k + 2] += lazy[k];
			}
			lazy[k] = 0;
		}
	}
	T query_raw(int a, int b, int l, int r, int k) {
		eval(k, l, r);
		if (b <= l || r <= a)return DEF;
		if (a <= l && r <= b)return seg[k];
		T vl = query_raw(a, b, l, (l + r) / 2, 2 * k + 1);
		T vr = query_raw(a, b, (l + r) / 2, r, 2 * k + 2);
		return min(vl, vr, Comp());
	}
	void update_raw(int a, int b, T x, int l, int r, int k) {
		eval(k, l, r);
		if (b <= l || r <= a)return;
		if (a <= l && r <= b) {
			lazy[k] += x;
			eval(k, l, r);
		}
		else {
			update_raw(a, b, x, l, (l + r) / 2, 2 * k + 1);
			update_raw(a, b, x, (l + r) / 2, r, 2 * k + 2);
			seg[k] = min(seg[2 * k + 1], seg[2 * k + 2], Comp());
		}
	}
public:
	//サイズn、デフォルト値defのセグ木を作る
	RMQ_starry(int n, T def) :DEF(def) {
		width = 1;
		while (width < n)width *= 2;
		seg.assign(width * 2 - 1, DEF);
		lazy.assign(seg.size(), T());
	}
	//区間[a,b)の答えを取得する
	T query(int a, int b) { return query_raw(a, b, 0, width, 0); }
	//区間[a,b)に一様に値xを加算する
	void update(int a, int b, T x) { update_raw(a, b, x, 0, width, 0); }
	//配列ごと初期化する
	void init(const vector<T>&vec) {
		for (int i = 0; i < min(width, (int)vec.size()); i++)
			seg[i + width - 1] = vec[i];
		for (int i = width - 2; i >= 0; i--)
			seg[i] = min(seg[i * 2 + 1], seg[i * 2 + 2], Comp());
		fill(lazy.begin(), lazy.end(), T());
	}
};

int main(void)
{
	cin >> S;
	M = S.size();
	int mid = -1;
	if (M % 2 == 1) {
		S.erase(M / 2, 1);
		M--;
		mid = M / 2;
	}
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int L, R; cin >> L >> R;
		L--;
		if (mid >= 0 && L > mid) {
			L--;
		}
		if (mid >= 0 && R > mid) {
			R--;
		}
		if (L == R)continue;//消滅
		if (R <= M / 2) {
			//左側にいるので何もしない
			vec.push_back({ L,R });
		}
		else if (L >= M / 2) {
			vec.push_back({ M - R,M - L });
		}
		else {
			//真ん中をまたいでいる
			int dl = abs(M / 2 - L);
			int dr = abs(M / 2 - R);
			if (dl == dr)continue;//消滅
			if (dl > dr) {
				//左側に寄せる
				vec.push_back({ L,M / 2 - dr });
			}
			else {
				//右側に寄せる
				int LL = M / 2 + dl;
				vec.push_back({ M - R,M - LL });
			}
		}
	}
	N = vec.size();
	string P = S.substr(0, M / 2);
	string Q = S.substr(M / 2);
	reverse(Q.begin(), Q.end());
	//PからQに変えていく
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>que;
	for (auto v : vec) {
		que.push(v);
	}
	//セグ木で管理
	RMQ_starry<LL, greater<LL>>Pseg(M / 2, -1);
	vector<LL>hina;
	for (int i = 0; i < M / 2; ++i) {
		hina.push_back(P[i] - 'a');
	}
	Pseg.init(hina);
	for (int i = 0; i < M / 2; ++i) {
		vector<int>Rset;
		while (!que.empty() && que.top().first == i) {
			if (que.top().second == i) {
				que.pop();
				continue;
			}
			Rset.push_back(que.top().second);
			que.pop();
		}
		if (Rset.empty())continue;
		pair<int, int>now = { i,Rset[0] };
		if (Rset.size() > 1) {
			for (int j = 1; j < Rset.size(); ++j) {
				que.push({ Rset[j - 1],Rset[j] });
			}
		}
		//nowに応じて大小をする
		LL res = Pseg.query(i, i + 1);
		LL mok = Q[i] - 'a';
		LL dif = mok - res;
		dif += 26 * 1234567890LL;
		assert(dif >= 0);
		dif %= 26;
		Pseg.update(now.first, now.second, dif);
	}

	for (int i = 0; i < M / 2; ++i) {
		LL let = Pseg.query(i, i + 1);
		LL val = Q[i] - 'a';
		if (val % 26 != let % 26) {
			cout << "NO\n";
			return 0;
		}
	}
	cout << "YES\n";
	return 0;
}