← 返回题目列表

Codeforces · 2069/E

E. A、B、AB 和 BA

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

给你一个由字符组成的字符串 $$$s$$$ A 和 B.

你的任务是将其分割成长度为 $$$1$$$ 和 $$$2$$$ 的块,这样

  • 等于 " 的字符串不超过 $$$a$$$A";
  • 等于 " 的字符串不超过 $$$b$$$B";
  • 不超过 $$$ab$$$ 字符串”AB";
  • 不超过 $$$ba$$$ 字符串”BA";

字符串“AA“和”BB“被禁止。初始字符串 $$$s$$$ 的每个字符都应该属于一个块。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是 $$$t$$$ 独立案例。

每个测试用例的第一行包含一个字符串 $$$s$$$ ($$$1 \le |s| \le 5 \cdot 10^5$$$) 仅由字符组成 A 和/或 B.

每个测试用例的第二行包含四个整数 $$$a$$$、$$$b$$$、$$$ab$$$ 和 $$$ba$$$ ($$$0 \le a, b, ab, ba \le 5 \cdot 10^5$$$) — 允许的最大字符串数量 "A", "B", "AB“,和”BA”相应地。

保证所有测试用例中 $$$s$$$ 的总长度不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,打印 是 是否可以分割字符串$$$s$$$。否则,打印 NO.

示例

输入
复制

7
A
0 0 10 10
B
0 1 0 0
ABA
0 0 1 1
ABBABAAB
5 5 0 0
ABABBAABBAAB
1 1 2 3
ABBBBAB
0 3 2 0
BAABBA
1 3 2 0

输出
复制

NO
YES
NO
YES
YES
YES
NO

注意

在第三个测试用例中,所有可能的拆分为: A|B|A, AB|A or A|BA。他们都至少有一个“A".

在第四个测试用例中,可能的拆分之一如下: A|B|B|A|B|A|A|B.

在第五个测试用例中,可能的拆分之一如下: A|BA|B|BA|AB|BA|AB.