E - Combination Lock Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

りんごさんは文字列 S を持っています。

りんごさんは以下のような N 種類の操作を好きな順番で何回でも行うことができます。

  • 操作 i：S の L_i 文字目から R_i 文字目までをそれぞれ次のアルファベットにする。（a は b に、b は c に・・・）ただし、z の次のアルファベットは a であるとする。

回文が大好きなりんごさんは S を回文にしようとしています。 これが可能かどうかを判定してください。

制約

  • 1 \leq |S| \leq 10^5
  • S は小文字アルファベットのみからなる。
  • 1 \leq N \leq 10^5
  • 1 \leq L_i \leq R_i \leq |S|

入力

入力は以下の形式で標準入力から与えられる。

S
N
L_1 R_1
L_2 R_2
:
L_N R_N

出力

S を回文にできるなら YES を、できないなら NO を出力せよ。

入力例 1

bixzja
2
2 3
3 6

出力例 1

YES

例えば、操作 1、操作 2、操作 1 の順に行うと、bixzja → bjyzja → bjzakb → bkaakb と変化し、回文になります。

入力例 2

abc
1
2 2

出力例 2

NO

入力例 3

cassert
4
1 2
3 4
1 1
2 2

出力例 3

YES

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