CF2107C Maximum Subarray Sum

You are given an array $ a_1,a_2,\ldots,a_n $ of length $ n $ and a positive integer $ k $ , but some parts of the array $ a $ are missing. Your task is to fill the missing part so that the maximum subarray sum $ ^{\text{∗}} $ of $ a $ is exactly $ k $ , or report that no solution exists. Formally, you are given a binary string $ s $ and a partially filled array $ a $ , where: - If you remember the value of $ a_i $ , $ s_i = 1 $ to indicate that, and you are given the real value of $ a_i $ . - If you don't remember the value of $ a_i $ , $ s_i = 0 $ to indicate that, and you are given $ a_i = 0 $ . All the values that you remember satisfy $ |a_i| \le 10^6 $ . However, you may use values up to $ 10^{18} $ to fill in the values that you do not remember. It can be proven that if a solution exists, a solution also exists satisfying $ |a_i| \le 10^{18} $ . $ ^{\text{∗}} $ The maximum subarray sum of an array $ a $ of length $ n $ , i.e. $ a_1, a_2, \ldots a_n $ is defined as $ \max_{1 \le i \le j \le n} S(i, j) $ where $ S(i, j) = a_i + a_{i + 1} + \ldots + a_j $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two numbers $ n,k $ ( $ 1 \le n \le 2 \cdot 10^5,1 \le k \le 10^{12} $ ). The second line of each test case contains a binary ( $ \texttt{01} $ ) string $ s $ of length $ n $ . The third line of each test case contains $ n $ numbers $ a_1,a_2,\ldots,a_n $ ( $ |a_i| \le 10^6 $ ). If $ s_i = \texttt{0} $ , then it's guaranteed that $ a_i = 0 $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, first output $ \texttt{Yes} $ if a solution exists or $ \texttt{No} $ if no solution exists. You may print each character in either case, for example $ \texttt{YES} $ and $ \texttt{yEs} $ will also be accepted. If there's at least one solution, print $ n $ numbers $ a_1,a_2,\ldots,a_n $ on the second line. $ |a_i| \le 10^{18} $ must hold.

In test case $ 1 $ , only the first position is not filled. We can fill it with $ 4 $ to get the array $ [4, 0, 1] $ which has maximum subarray sum of $ 5 $ . In test case $ 2 $ , only the third position is not filled. We can fill it with $ 5 $ to get the array $ [4, -3, 5, -2, 1] $ . Here the maximum subarray sum comes from the subarray $ [4, -3, 5] $ and it is $ 6 $ , as required. In test case $ 3 $ , the first and second positions are unfilled. We can fill both with $ 2 $ to get the array $ [2, 2, -4, -5] $ which has a maximum subarray sum of $ 4 $ . Note that other outputs are also possible such as $ [0, 4, -4, -5] $ . In test case $ 4 $ , it is impossible to get a valid array. For example, if we filled the third position with $ 0 $ , we get $ [1, 2, 0, 5, -1, 9] $ , but this has a maximum subarray sum of $ 16 $ , not $ 12 $ as required.