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
withb
, replaceb
withc
and so on.) Forz
, we assume that its succeeding letter isa
.
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