在使用 De Bruijn 固定长度比特串序列未能找到一个女孩后,Blackslex 将注意力转向了政治。
由于他的高魅力,他现在负责为他的国家的 $$$n$$$ 选区划定边界。在Blackslex的国家里,A党有$$$x$$$选民,B党有$$$y$$$选民。利用他惊人的绘画技巧,他可以将任何政党的选民分配到他选择的任何选区。
他的比特串历史让他想知道是否可以分配选民,使每个选区的获胜者遵循某种比特串模式。为了避免怀疑,他还必须将至少 $$$p_i$$$ 选民分配到每个选区。告诉他是否可以!
正式地,您将获得一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$、一个长度为 $$$n$$$ 的数组 $$$p$$$ 以及两个整数 $$$x$$$ 和 $$$y$$$。
您想要确定是否存在两个长度为 $$$n$$$ 的非负整数数组 $$$a$$$ 和 $$$b$$$ 满足以下条件:
- $$$a_1 + a_2 + \dots + a_n = x$$$
- $$$b_1 + b_2 + \dots + b_n = y$$$
- 对于每个 $$$1 \leq i \leq n$$$,$$$a_i + b_i \geq p_i$$$
- 对于每个 $$$1 \leq i \leq n$$$:
- 如果 $$$s_i = 0$$$ 则 $$$a_i \gt b_i$$$
- 如果 $$$s_i = 1$$$ 则 $$$b_i \gt a_i$$$
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$、$$$1 \leq x, y \leq 10^9$$$)。
第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$。
第三行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$1 \leq p_i \leq 10^9$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印(不区分大小写) 是 如果存在满足所有条件的数组 $$$a, b$$$,或者 NO 否则。
示例
输入复制
63 5 50102 4 34 2 300011 1 1 12 4 2003 34 23 2011112 2 2 21 25 260512 4 2003 4
输出复制
YESNOYESNONONO
注意
在第一个测试用例中,选民的可能分布之一是:$$$a = [2, 0, 3]$$$ 和 $$$b = [0, 4, 1]$$$。
在第三个测试用例中,选民的可能分布之一是:$$$a = [2, 2]$$$ 和 $$$b = [1, 1]$$$。
对于其他测试用例,可以证明不存在满足条件的选民分布。