给定一个数组 $$$a_1,a_2,\ldots,a_n$$$,长度为 $$$n$$$ 和一个正整数 $$$k$$$,但数组 $$$a$$$ 的某些部分丢失。你的任务是填补缺失的部分,以便 最大子数组和$$$a$$$ 的 $$$^{\text{∗}}$$$ 恰好是 $$$k$$$,或者报告不存在解。
正式地,您将获得一个二进制字符串 $$$s$$$ 和一个部分填充的数组 $$$a$$$,其中:
- 如果您还记得 $$$a_i$$$ 的值,则 $$$s_i = 1$$$ 可以表明这一点,并且您将获得 $$$a_i$$$ 的实际值。
- 如果您不记得 $$$a_i$$$ 的值,则 $$$s_i = 0$$$ 来表示,并且您将得到 $$$a_i = 0$$$。
您记住的所有值都满足 $$$|a_i| \le 10^6$$$。但是,您可以使用最大 $$$10^{18}$$$ 的值来填写您不记得的值。可以证明,如果存在解,则也存在满足$$$|a_i|的解。 \le 10^{18}$$$。
$$$^{\text{*}}$$$The 长度为 $$$n$$$ 的数组 $$$a$$$ 的 最大子数组和 ,即 $$$a_1, a_2, \ldots a_n$$$ 定义为 $$$\max_{1 \le i \le j \le n} S(i, j)$$$ 其中 $$$S(i, j) = a_i + a_{i + 1} + \ldots + a_j$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个数字 $$$n,k$$$ ($$$1 \le n \le 2 \cdot 10^5,1 \le k \le 10^{12}$$$)。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制 ($$$\texttt{01}$$$) 字符串 $$$s$$$。
每个测试用例的第三行包含 $$$n$$$ 数字 $$$a_1,a_2,\ldots,a_n$$$ ($$$|a_i| \le 10^6$$$)。如果$$$s_i = \texttt{0}$$$,则保证$$$a_i = 0$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果存在解决方案,则首先输出 $$$\texttt{Yes}$$$;如果不存在解决方案,则首先输出 $$$\texttt{No}$$$。您可以在任一情况下打印每个字符,例如 $$$\texttt{YES}$$$ 和 $$$\texttt{yEs}$$$ 也将被接受。
如果至少有一个解决方案,请在第二行打印 $$$n$$$ 数字 $$$a_1,a_2,\ldots,a_n$$$。 $$$|a_i| \le 10^{18}$$$ 必须成立。
示例
输入复制
103 50110 0 15 6110114 -3 0 -2 14 400110 0 -4 -56 121101111 2 0 5 -1 95 19000000 0 0 0 05 1911001-8 6 0 0 -55 101010110 0 10 0 101 1103 51113 -1 34 51011-2 0 1 -5
输出复制
Yes 4 0 1 Yes 4 -3 5 -2 1 Yes 2 2 -4 -5 No Yes 5 1 9 2 2 Yes -8 6 6 7 -5 Yes 10 -20 10 -20 10 No Yes 3 -1 3 Yes -2 4 1 -5
注意
在测试用例 $$$1$$$ 中,只有第一个位置未填充。我们可以用 $$$4$$$ 填充它,得到数组 $$$[4, 0, 1]$$$,它的最大子数组和为 $$$5$$$。
在测试用例$$$2$$$中,只有第三个位置没有被填充。我们可以用$$$5$$$填充它来得到数组$$$[4, -3, 5, -2, 1]$$$。这里最大子数组和来自子数组$$$[4, -3, 5]$$$,根据要求它是$$$6$$$。
在测试用例 $$$3$$$ 中,第一个和第二个位置未填充。我们可以用 $$$2$$$ 填充两者,得到数组 $$$[2, 2, -4, -5]$$$,它的最大子数组和为 $$$4$$$。请注意,其他输出也是可能的,例如 $$$[0, 4, -4, -5]$$$。
在测试用例 $$$4$$$ 中,不可能获得有效的数组。例如,如果我们用 $$$0$$$ 填充第三个位置,我们会得到 $$$[1, 2, 0, 5, -1, 9]$$$,但是它的最大子数组总和为 $$$16$$$,而不是要求的 $$$12$$$。