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 <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

int vis[100010];
vector<int> g[100010],a;

int get(int pos){
	int v=a[pos]; vis[pos]=1;
	for(auto x:g[pos]) if(!vis[x]) v+=get(x);
	return v%26;
}

int main(){FIN;
	string s; int q; cin>>s>>q;
	s="a"+s+"a";
	fore(i,1,SZ(s)) a.pb((s[i]-s[i-1]+26)%26);
	int n=SZ(a);
	fore(i,0,n) g[i].pb(n-i-1);
	while(q--){
		int l,r;cin>>l>>r;
		g[l-1].pb(r); g[r].pb(l-1);
	}
	fore(i,0,n) if(!vis[i]&&get(i)) cout << "NO\n",exit(0);
	cout<<"YES\n";
}