E. A, B, AB и BA
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана строка $$$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$$$ по всем наборам входных данных.

Выходные данные

Для каждого набора входных данных выведите YES, если возможно разбить строку $$$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 или A|BA. Все они имеют хотя бы одну «A».

В четвертом наборе входных данных одно из возможных разбиений следующее: A|B|B|A|B|A|A|B.

В пятом наборе входных данных одно из возможных разбиений следующее: A|BA|B|BA|AB|BA|AB.