521 与“我爱你”的中文发音相同。在这个特殊的日子里,小S想给小A一些精心准备的片段,以回忆他们多年的友谊。
小S准备了一个数组$$$a_1,a_2,\ldots,a_n$$$。让我们定义它的前缀和数组 $$$b_1, b_2, \ldots, b_n$$$,其中 $$$b_i = a_1 + a_2 + \ldots + a_i$$$。还定义 $$$b$$$ 的前缀最大数组:$$$c_1, c_2, \ldots, c_n$$$,其中 $$$c_i = \max(b_1, b_2, \ldots, b_i)$$$。
现在数组$$$a$$$已经部分丢失,幸好小S还保留着数组$$$c$$$。你的任务是恢复数组$$$a$$$并发送给小A,或者报告不存在这样的数组——这样的话,善良可爱的小A也不会生气。
正式地,您将获得一个二进制字符串 $$$s$$$、一个部分填充的数组 $$$a$$$ 和一个数组 $$$c$$$,其中:
- 如果您记住 $$$a_i$$$ 的值,则 $$$s_i = 1$$$,并且您将获得 $$$a_i$$$ 的真实值。
- 如果您不记得 $$$a_i$$$ 的值,则 $$$s_i = 0$$$,并且您将得到 $$$a_i = 0$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ ($$$s_i \in \{\texttt{0}, \texttt{1}\}$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \le 10^6$$$)。如果$$$s_i = \texttt{0}$$$,则保证$$$a_i = 0$$$。
每个测试用例的第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \ldots, c_n$$$ ($$$|c_i| \le 2 \cdot 10^{11}$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印“是" 如果数组 $$$a$$$ 存在则在第一行,否则打印 "No“。您可以在任何情况下打印答案。例如,”是的", "是", "NO", "nO”也将被接受。
如果至少有一个解,则在第二行打印 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$|a_i| \leq 10^{18}$$$)。如果有多个合适的数组,您可以打印其中任何一个。
示例
输入复制
10411101 2 -1 01 3 3 35000010 0 0 0 5-4 -4 -1 -1 -1110160011110 0 2 -3 3 -6-5 -2 0 0 0 05111101 2 0 5 01 2 2 7 62010 1-1 -160010100 0 5 0 3 03 3 4 9 13 1660001000 0 0 4 0 02 6 6 7 7 72000 04 -18111111116 1 1 2 0 5 1 96 7 8 10 10 15 16 25
输出复制
Yes 1 2 -1 0 Yes -4 0 3 -6 5 No Yes -5 3 2 -3 3 -6 No No No Yes 2 4 -3 4 -100 0 No Yes 6 1 1 2 0 5 1 9
注意
在第一个测试用例中,我们有:
- $$$a = [1, 2, -1, 0]$$$。
- $$$b = [1, 3, 2, 2]$$$。
- $$$c = [1, 3, 3, 3]$$$。
在第三个测试用例中,正确的数组 $$$a$$$ 应等于 $$$[1]$$$,因此不存在解决方案。