← 返回题目列表

AtCoder · cf17_final_e

E. 密码锁

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

林戈有一根绳子 S.

他可以执行以下操作 N 种操作可以任意顺序任意次数。

  • 操作 i:对于来自 L_i-th 通过 R_i- 第一个字符 S,将其替换为英文字母表中的后续字母。 (也就是说,替换 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

输出

打印 YES 如果可以转动 S 变成回文;打印 NO 如果不可能的话。


示例输入 1

bixzja
2
2 3
3 6

示例输出 1

YES

例如,如果我们执行操作 1, 2 和 1 按此顺序, S 更改为 bixzja → bjyzja → bjzakb → bkaakb 并成为回文。


示例输入 2

abc
1
2 2

示例输出 2

NO

示例输入 3

cassert
4
1 2
3 4
1 1
2 2

示例输出 3

YES