Problem Description

Ringo has a string $ S $.

Ringo can perform the following $ N $ types of operations in any order and as many times as he likes:

• Operation $ i $: Change each character from the $ L_i $-th to the $ R_i $-th character of $ S $ to the next alphabetically (e.g., a becomes b, b becomes c, etc.). However, z wraps around to a.

Ringo loves palindromes and is trying to make $ S $ a palindrome. Determine if this is possible.

Input Format

The input is given from the standard input in the following format:

$ S $ $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ : $ $ L_N $ $ R_N $

Output Format

Output YES if $ S $ can be made into a palindrome, otherwise output NO.

Sample Input and Output

Sample Input #1

bixzja
2
2 3
3 6

Sample Output #1

YES

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

Notes/Hints

Constraints

• $1 \leq |S| \leq 10^5$
• $ S $ consists only of lowercase alphabets.
• $1 \leq N \leq 10^5$
• $1 \leq L_i \leq R_i \leq |S|$

Sample Explanation 1

For example, if you perform operation $ 1 $, then operation $ 2 $, and then operation $ 1 $ again, bixzja changes to bjyzja → bjzakb → bkaakb, which becomes a palindrome.

见题面 Input 部分

见题面 Output 部分