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 REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

string S;
ll N, L[200000], R[200000];
vector<ll> E[200000];
vector<ll> d;
bool visited[200000];

ll dfs(ll v) {
  if(visited[v]) return 0;
  visited[v] = true;

  ll ret = d[v];
  for(ll u : E[v]) ret += dfs(u);
  return ret;
}

int main(void) {
  cin >> S >> N;
  REP(i, 0, N) cin >> L[i] >> R[i], L[i]--, R[i];

  S = "a" + S + "a";
  REP(i, 0, S.length() - 1) d.push_back((S[i + 1] - S[i] + 26) % 26);

  REP(i, 0, N) {
    E[L[i]].push_back(R[i]);
    E[R[i]].push_back(L[i]);
  }
  REP(i, 0, (d.size()) / 2) {
    E[i].push_back(d.size() - 1 - i);
    E[d.size() - 1 - i].push_back(i);
  }

  bool ans = true;
  REP(i, 0, d.size()) visited[i] = false;
  REP(i, 0, d.size()) {
    ll sum = dfs(i) % 26;
    if(sum != 0) ans = false;
  }
  cout << (ans ? "YES" : "NO") << endl;
}