CF2107C.Maximum Subarray Sum

给你一个长为 $n$ 的序列 $a=(a_1,a_2,\cdots,a_n)$，$a$ 的一部分丢失了。你的任务是填补丢失的部分使得 $a$ 的最大子区间和为 $k$，或报告无解。

给你一个 01 串 $s$ 和 $a$：

• 如果 $a_i$ 没有被丢失，$s_i=1$，此时 $a_i$ 记录了它的真实值。
• 如果 $a_i$ 被丢失，$s_i=0$，此时给到你的序列 $a$ 中 $a_i=0$。

输入的 $a$ 满足 $\vert a_i\vert\le 10^6$，你填充后的 $a$ 需要满足 $\vert a_i\vert \le 10^{18}$。可以被证明如果存在解，那么一定存在一个满足 $\vert a_i\vert \le 10^{18}$ 的解。

一个长为 $n$ 的数列 $a$ 的最大子区间和是 $\max\limits_{1\le i\le j\le n}\sum\limits_{k=i}^j a_k$。

多组数据，第一行一个整数为数据组数 $t(1\le t\le 10^4)$。

对于每组数据，第一行两个整数 $n,k(1\le n\le 2\times 10^5,1\le k\le 10^{12})$。
第二行为一个长为 $n$ 的 01 字符串 $s$。
第三行 $n$ 个整数 $a_1,a_2,\cdots,a_n(\vert a_i\vert\le 10^6)$。保证 $s_i=0$ 时 $a_i=0$。

保证一个测试点中 $\sum n\le 2\times 10^5$。

对于每组数据，第一行一个字符串，如果有解输出 Yes，如果无解输出 No。大小写不敏感。

如果有解，第二行输出填充后的字符串 $a$。你需要保证 $\vert a_i\vert\le 10^{18}$。

如果有多种解法，输出任意一种均可。

第一组数据中，向唯一丢失的 $a_1$ 填充 $4$ 得到 $a=(4,0,1)$，它的最大子区间和为 $5$。

第二组数据中，向唯一丢失的 $a_3$ 填充 $5$ 得到 $a=(4,-3,5,-2,1)$，它的最大子区间和为 $6$。

第三组数据中 $a_1$ 和 $a_2$ 待填充，向它们填充 $2$ 得到 $a=(2,2,-4,-5)$，它的最大子区间和为 $4$。$a=(0,4,-4,-5)$ 也是一种解法。

对于第四组数据，没有合法的填充 $a$ 的方式。例如 $a=(1,2,0,5,-1,9)$，它的最大子区间和为 $16$ 而非 $12$。

By chenxi2009