← 返回题目列表

AtCoder · arc071_c

E. 变换

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

分数: 600 点

问题陈述

让我们考虑对由以下内容组成的字符串进行以下操作 A 和 B:

  1. 选择字符串中的一个字符。如果是的话 A,替换为 BB。如果是的话 B,替换为 AA.
  2. 选择一个等于以下任一的子字符串 AAA or BBB,并将其从字符串中删除。

例如,如果第一个操作执行于 ABA 并选择第一个字符,字符串变为 BBBA。 如果执行第二次操作 选择 BBBAAAA 并选择第四到第六个字符,字符串变为 BBBA.

这些操作可以按任意顺序执行任意次数。

给你两个字符串 S 和 T,和 q 查询 a_i, b_i, c_i, d_i。 对于每个查询,确定是否 S_{a_i} S_{{a_i}+1} ... S_{b_i},一个子串 S,可以制成 T_{c_i} T_{{c_i}+1} ... T_{d_i},一个子串 T.

约束

  • 1 \leq |S|, |T| \leq 10^5
  • S 和 T 由字母组成 A 和 B.
  • 1 \leq q \leq 10^5
  • 1 \leq a_i \leq b_i \leq |S|
  • 1 \leq c_i \leq d_i \leq |T|

输入

输入由标准输入按以下格式给出:

S
T
q
a_1 b_1 c_1 d_1
...
a_q b_q c_q d_q

输出

打印 q 行。的 i- 第行应包含对 i第一个查询。如果 S_{a_i} S_{{a_i}+1} ... S_{b_i} 可以制成 T_{c_i} T_{{c_i}+1} ... T_{d_i},打印 YES。否则,打印 NO.


示例输入 1

BBBAAAABA
BBBBA
4
7 9 2 5
7 9 1 4
1 7 2 5
1 7 2 4

示例输出 1

YES
NO
YES
NO

第一个查询询问字符串是否 ABA 可以制成 BBBA。 正如问题陈述中所解释的,可以通过第一个操作来完成。

第二个查询询问是否 ABA 可以制成 BBBB,第四个查询询问是否 BBBAAAA 可以制成 BBB。 两者都不可能。

第三个查询询问字符串是否 BBBAAAA 可以制成 BBBA。 正如问题陈述中所解释的,可以通过第二个操作来完成。


示例输入 2

AAAAABBBBAAABBBBAAAA
BBBBAAABBBBBBAAAAABB
10
2 15 2 13
2 13 6 16
1 13 2 20
4 20 3 20
1 18 9 19
2 14 1 11
3 20 3 15
6 16 1 17
4 18 8 20
7 20 3 14

示例输出 2

YES
YES
YES
YES
YES
YES
NO
NO
NO
NO