p03537 CODE FESTIVAL 2017 Final (Parallel) - Combination Lock
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
```python
import sys
from operator import sub

sys.setrecursionlimit(100000)


def dfs(s, visited):
    visited.add(s)
    for v in links[s]:
        if v not in visited:
            dfs(v, visited)


def solve():
    checked = set()
    for i in range(ls // 2 + 1):
        if i in checked:
            continue
        visited = set()
        dfs(i, visited)
        inner_total = sum(sd[k] for k in visited) % 26
        if inner_total != 0:
            return False
        checked.update(visited)
    return True


s = input()
sl = list(map(ord, s))
sd = list(map(sub, sl + [97], [97] + sl))
ls = len(s)
lsd = len(sd)

n = int(input())
links = [set() for _ in range(lsd)]

for i in range((ls + 1) // 2):
    links[i].add(ls - i)
    links[ls - i].add(i)
for a, b in (map(int, input().split()) for _ in range(n)):
    links[a - 1].add(b)
    links[b].add(a - 1)

print('YES' if solve() else 'NO')

```