当前没有测试数据。

题目描述

给定一个长度为 $n$ 的数组 $a_1, a_2, \ldots, a_n$ 和一个正整数 $k$，但数组 $a$ 的某些部分缺失。你的任务是填充缺失的部分，使得数组 $a$ 的最大子数组和恰好等于 $k$，或者报告无解。

形式上，给定一个二进制字符串 $s$ 和一个部分填充的数组 $a$，其中：

• 若 $s_i = 1$，表示你记得 $a_i$ 的值，此时给定 $a_i$ 的真实值；
• 若 $s_i = 0$，表示你不记得 $a_i$ 的值，此时给定 $a_i = 0$（仅为占位符）。

所有你记得的值满足 $|a_i| \le 10^6$。你可以用绝对值不超过 $10^{18}$ 的任意整数填充缺失的值。可以证明，若存在解，则一定存在满足 $|a_i| \le 10^{18}$ 的解。

注：数组 $a$ 的最大子数组和定义为 $\max_{1 \le i \le j \le n} S(i, j)$，其中 $S(i, j) = a_i + a_{i+1} + \ldots + a_j$。

输入格式

第一行包含测试用例数 $t$。

每个测试用例：

• 第一行包含两个整数 $n$ 和 $k$。
• 第二行包含一个长度为 $n$ 的二进制字符串 $s$。
• 第三行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$。若 $s_i = 0$，则保证 $a_i = 0$。

输出格式

对于每个测试用例：

• 若存在解，输出 Yes，并在下一行输出填充后的数组 $a_1, a_2, \ldots, a_n$；
• 若无解，输出 No。

输出字符串不区分大小写。

样例

10
3 5
011
0 0 1
5 6
11011
4 -3 0 -2 1
4 4
0011
0 0 -4 -5
6 12
110111
1 2 0 5 -1 9
5 19
00000
0 0 0 0 0
5 19
11001
-8 6 0 0 -5
5 10
10101
10 0 10 0 10
1 1
1
0
3 5
111
3 -1 3
4 5
1011
-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 \le t \le 10^4$
• $1 \le n \le 2 \cdot 10^5$
• $1 \le k \le 10^{12}$
• $|a_i| \le 10^6$
• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$