CF1659B Bit Flipping

You are given a binary string of length $ n $ . You have exactly $ k $ moves. In one move, you must select a single bit. The state of all bits except that bit will get flipped ( $ 0 $ becomes $ 1 $ , $ 1 $ becomes $ 0 $ ). You need to output the lexicographically largest string that you can get after using all $ k $ moves. Also, output the number of times you will select each bit. If there are multiple ways to do this, you may output any of them. A binary string $ a $ is lexicographically larger than a binary string $ b $ of the same length, if and only if the following holds: - in the first position where $ a $ and $ b $ differ, the string $ a $ contains a $ 1 $ , and the string $ b $ contains a $ 0 $ .

The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. Each test case has two lines. The first line has two integers $ n $ and $ k $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ; $ 0 \leq k \leq 10^9 $ ). The second line has a binary string of length $ n $ , each character is either $ 0 $ or $ 1 $ . The sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output two lines. The first line should contain the lexicographically largest string you can obtain. The second line should contain $ n $ integers $ f_1, f_2, \ldots, f_n $ , where $ f_i $ is the number of times the $ i $ -th bit is selected. The sum of all the integers must be equal to $ k $ .

Here is the explanation for the first testcase. Each step shows how the binary string changes in a move. - Choose bit $ 1 $ : $ \color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110} $ . - Choose bit $ 4 $ : $ \color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01} $ . - Choose bit $ 4 $ : $ \color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10} $ . The final string is $ 111110 $ and this is the lexicographically largest string we can get.