Problem:


Score : 1000 points

Problem Statement

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.

Sample Input 1

bixzja
2
2 3
3 6

Sample Output 1

YES

For example, if we perform Operation 1, 2 and 1 in this order, S changes as bixzja → bjyzja → bjzakb → bkaakb and becomes a palindrome.

Sample Input 2

abc
1
2 2

Sample Output 2

NO

Sample Input 3

cassert
4
1 2
3 4
1 1
2 2

Sample Output 3

YES



Sample input:
bixzja
2
2 3
3 6


Sample output:
YES

Submission status: Accepted

Solution code:
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')