Alina has discovered a weird language, which contains only $4$ words: ${A}$, ${B}$, ${AB}$, ${BA}$. It also turned out that there are no spaces in this language: a sentence is written by just concatenating its words into a single string.

Alina has found one such sentence $s$ and she is curious: is it possible that it consists of precisely $a$ words ${A}$, $b$ words ${B}$, $c$ words ${AB}$, and $d$ words ${BA}$?

In other words, determine, if it's possible to concatenate these $a+b+c+d$ words in some order so that the resulting string is $s$. Each of the $a+b+c+d$ words must be used exactly once in the concatenation, but you can choose the order in which they are concatenated.


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains four integers $a$, $b$, $c$, $d$ ($0\le a,b,c,d\le 2\cdot 10^5$) — the number of times that words ${A}$, ${B}$, ${AB}$, ${BA}$ respectively must be used in the sentence.

The second line contains the string $s$ ($s$ consists only of the characters ${A}$ and ${B}$, $1\le |s| \le 2\cdot 10^5$, $|s|=a+b+2c+2d$)  — the sentence. Notice that the condition $|s|=a+b+2c+2d$ (here $|s|$ denotes the length of the string $s$) is equivalent to the fact that $s$ is as long as the concatenation of the $a+b+c+d$ words.

The sum of the lengths of $s$ over all test cases doesn't exceed $2\cdot 10^5$.


-----Output-----

For each test case output ${YES}$ if it is possible that the sentence $s$ consists of precisely $a$ words ${A}$, $b$ words ${B}$, $c$ words ${AB}$, and $d$ words ${BA}$, and ${NO}$ otherwise. You can output each letter in any case.


-----Examples-----

Input
8
1 0 0 0
B
0 0 1 0
AB
1 1 0 1
ABAB
1 0 1 1
ABAAB
1 1 2 2
BAABBABBAA
1 1 2 3
ABABABBAABAB
2 3 5 4
AABAABBABAAABABBABBBABB
1 3 3 10
BBABABABABBBABABABABABABAABABA
Output
NO
YES
YES
YES
YES
YES
NO
YES


-----Note-----

In the first test case, the sentence $s$ is ${B}$. Clearly, it can't consist of a single word ${A}$, so the answer is ${NO}$.

In the second test case, the sentence $s$ is ${AB}$, and it's possible that it consists of a single word ${AB}$, so the answer is ${YES}$.

In the third test case, the sentence $s$ is ${ABAB}$, and it's possible that it consists of one word ${A}$, one word ${B}$, and one word ${BA}$, as ${A} + {BA} + {B} = {ABAB}$.

In the fourth test case, the sentence $s$ is ${ABAAB}$, and it's possible that it consists of one word ${A}$, one word ${AB}$, and one word ${BA}$, as ${A} + {BA} + {AB} = {ABAAB}$.

In the fifth test case, the sentence $s$ is ${BAABBABBAA}$, and it's possible that it consists of one word ${A}$, one word ${B}$, two words ${AB}$, and two words ${BA}$, as ${BA} + {AB} + {B} + {AB} + {BA} + {A}= {BAABBABBAA}$.

Difficulty: HARD
Tags: String algorithms

Sorting

Implementation

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
import sys

def solve():
	inp = sys.stdin.readline
	(a, b, c, d) = map(int, inp().split())
	s = inp()
	if s.count('A') != a + c + d or s.count('B') != b + c + d:
		print('NO')
		return
	cc = {'A': [], 'B': []}
	f = 0
	e = 0
	for i in range(1, len(s) - 1):
		if s[i] == s[i - 1]:
			l = i - f
			if l % 2 == 0:
				cc[s[f]].append(l // 2)
			else:
				e += l // 2
			f = i
	l = len(s) - 1 - f
	if l % 2 == 0:
		cc[s[f]].append(l // 2)
	else:
		e += l // 2
	ca = cc['A']
	ca.sort(reverse=True)
	while ca and c > 0:
		w = min(ca[-1], c)
		ca[-1] -= w
		c -= w
		if ca[-1] == 0:
			ca.pop()
	cb = cc['B']
	cb.sort(reverse=True)
	while cb and d > 0:
		w = min(cb[-1], d)
		cb[-1] -= w
		d -= w
		if cb[-1] == 0:
			cb.pop()
	for i in ca:
		e += i - 1
	for i in cb:
		e += i - 1
	if c + d <= e:
		print('YES')
	else:
		print('NO')

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import sys
input = sys.stdin.readline

def solve():
	(a, b, c, d) = map(int, input().split())
	s = input().strip()
	n = len(s)
	cnt = 0
	for i in range(n):
		if s[i] == 'A':
			cnt += 1
	if cnt != a + c + d:
		return 'NO'
	prev = -1
	cnt = 0
	r = []
	for i in range(n):
		if prev == s[i]:
			r.append((cnt, prev))
			cnt = 1
		else:
			cnt += 1
			prev = s[i]
	r.append((cnt, prev))
	r.sort()
	e = 0
	for (length, lc) in r:
		if length % 2 == 0:
			if lc == 'B' and length // 2 <= c:
				c -= length // 2
			elif lc == 'A' and length // 2 <= d:
				d -= length // 2
			else:
				e += length // 2 - 1
		else:
			e += length // 2
	return 'YES' if e >= c + d else 'NO'
for _ in range(int(input())):
	print(solve())


def solve():
	(a, b, ab, ba) = list(map(int, input().split()))
	s = input().strip()
	a_n = s.count('A')
	b_n = s.count('B')
	if a + ab + ba != a_n:
		return False
	elif b + ab + ba != b_n:
		return False
	abab_lens = []
	baba_lens = []
	ab_or_ba_count = 0
	prev_symbol = None
	start_symbol = s[0]
	start_index = 0
	for (i, c) in enumerate(list(s) + [s[-1]]):
		if c == prev_symbol:
			part_len = i - start_index
			if part_len > 1:
				if part_len % 2 == 1:
					ab_or_ba_count += part_len // 2
				elif c == 'B':
					abab_lens += [part_len // 2]
				else:
					baba_lens += [part_len // 2]
			start_index = i
			start_symbol = c
		prev_symbol = c
	for l in sorted(abab_lens):
		if ab >= l:
			ab -= l
		else:
			ab_or_ba_count += l - 1
	for l in sorted(baba_lens):
		if ba >= l:
			ba -= l
		else:
			ab_or_ba_count += l - 1
	return ab + ba <= ab_or_ba_count
n = int(input())
for i in range(n):
	if solve():
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(a, b, ab, ba) = map(int, input().split())
	s = input()
	if s.count('A') != a + ab + ba:
		print('NO')
		continue
	stack = [[1, s[0]]]
	for i in range(1, len(s)):
		if stack[-1][1] != s[i]:
			x = stack.pop()
			stack.append([x[0] + 1, s[i]])
		else:
			stack.append([1, s[i]])
	stack.sort()
	trash = 0
	for (val, ele) in stack:
		if not val % 2:
			if ele == 'A' and ba >= val // 2:
				ba -= val // 2
			elif ele == 'B' and ab >= val // 2:
				ab -= val // 2
			else:
				trash += val // 2 - 1
		else:
			trash += val // 2
	print('YES' if trash >= ab + ba else 'NO')


tc = int(input())
for _ in range(tc):
	(a, b, c, d) = list(map(int, input().split()))
	s = input()
	if s.count('A') != a + c + d:
		print('NO')
		continue
	x = 'X'
	k = 0
	z = []
	for i in s:
		if i == x:
			z.append((k, x))
			k = 1
		else:
			x = i
			k += 1
	z.append((k, x))
	r = 0
	z.sort()
	for (k, v) in z:
		if k % 2 == 0:
			if v == 'A' and d >= k // 2:
				d -= k // 2
			elif v == 'B' and c >= k // 2:
				c -= k // 2
			else:
				r += k // 2 - 1
		else:
			r += k // 2
	if r >= c + d:
		print('YES')
	else:
		print('NO')


t = int(input())
pp = 0
for _ in range(t):
	(a, b, c, d) = [int(i) for i in input().split()]
	s = input()
	if s.count('A') != a + c + d or s.count('B') != b + c + d:
		print('NO')
		continue
	l = len(s)
	ult = 'X'
	k = 0
	z = []
	for i in range(l):
		if s[i] == ult:
			z.append((k, ult))
			k = 1
		else:
			ult = s[i]
			k += 1
	z.append((k, ult))
	r = 0
	z.sort()
	for i in z:
		if i[0] % 2 == 0:
			if i[1] == 'A' and d >= i[0] // 2:
				d -= i[0] // 2
			elif i[1] == 'B' and c >= i[0] // 2:
				c -= i[0] // 2
			else:
				r += i[0] // 2 - 1
		else:
			r += i[0] // 2
	print('YES' if r >= c + d else 'NO')


def solve():
	(cnt_a, cnt_b, cnt_ab, cnt_ba) = map(int, input().strip().split())
	s = input()
	if s.count('A') != cnt_a + cnt_ba + cnt_ab:
		print('NO')
		return
	stk = [[1, s[0]]]
	for i in range(1, len(s)):
		if i == 0:
			continue
		c = s[i]
		if c != stk[-1][1]:
			x = stk.pop()
			stk.append([x[0] + 1, c])
		else:
			stk.append([1, c])
	stk.sort()
	rest = 0
	for (cnt, last) in stk:
		if not cnt % 2:
			if last == 'A' and cnt_ba >= cnt >> 1:
				cnt_ba -= cnt >> 1
			elif last == 'B' and cnt_ab >= cnt >> 1:
				cnt_ab -= cnt >> 1
			else:
				rest += (cnt >> 1) - 1
		else:
			rest += cnt >> 1
	if rest >= cnt_ab + cnt_ba:
		print('YES')
	else:
		print('NO')
t = int(input())
for _ in range(t):
	solve()


I = input
for _ in range(int(I())):
	(a, b, c, d) = map(int, I().split())
	s = I()
	if s.count('A') != a + c + d:
		print('NO')
		continue
	(i, n, segs) = (0, len(s), [])
	while i < n:
		j = i
		while i + 1 < n and s[i + 1] != s[i]:
			i += 1
		segs.append((i - j + 1, s[i]))
		i += 1
	segs.sort()
	trash = 0
	for (siz, ch) in segs:
		cnt = siz // 2
		if siz & 1 == 0:
			if ch == 'A' and d >= cnt:
				d -= cnt
			elif ch == 'B' and c >= cnt:
				c -= cnt
			else:
				trash += cnt - 1
		else:
			trash += cnt
	print('YES' if trash >= c + d else 'NO')


import sys, os, io
for _ in range(int(input())):
	c = [int(i) for i in input().split()]
	s = list(input().strip())
	if s.count('A') != c[0] + c[2] + c[3] or s.count('B') != c[1] + c[2] + c[3]:
		print('NO')
		continue
	n = len(s)
	a = [[s[0]]]
	for i in range(1, n):
		if s[i] == s[i - 1]:
			a.append([s[i]])
		else:
			a[-1].append(s[i])
	extra = 0
	for i in a:
		if len(i) % 2:
			c[ord(i[0]) - ord('A')] -= 1
			extra += len(i) // 2
	a.sort(key=lambda x: len(x))
	for i in a:
		if len(i) % 2 == 0:
			cnt = len(i) // 2
			if cnt <= c[2 + ord(i[0]) - ord('A')]:
				c[2 + ord(i[0]) - ord('A')] -= cnt
			else:
				extra += cnt - 1
	if min(c) < 0 or extra < c[2] + c[3]:
		print('NO')
	else:
		print('YES')