Bit Flipping
Contest: Codeforces Round 782 (Div. 2)
Difficulty rating: 1300
Tags: bitmasks, constructive algorithms, greedy, strings

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$$$.

Input format:
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$$$.

Output format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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}$$$.

Example input:
6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110

Example output:
111110
1 0 0 2 0 0 
111110
0 1 1 1 0 1 
000000
0 0 0 0 0 0 
100110
1 0 0 0 0 0 
111111
1 2 1 3 0 4 
111110
1 1 4 2 0 4

Editorial:
Let's see how many times a given bit will get flipped. Clearly, a bit gets flipped whenever it is not selected in an operation. Therefore, the $$$i$$$-th bit gets flipped $$$k-f_i$$$ times. We want to select a bit as few times as possible. Now we can handle a few cases.
1. $$$k$$$ is even, bit $$$i$$$ is $$$1$$$ $$$\Rightarrow$$$ $$$f_i=0$$$ (even number of flips don't change the bit)
2. $$$k$$$ is even, bit $$$i$$$ is $$$0$$$ $$$\Rightarrow$$$ $$$f_i=1$$$ (odd number of flips toggle the bit from $$$0$$$ to $$$1$$$)
3. $$$k$$$ is odd, bit $$$i$$$ is $$$1$$$ $$$\Rightarrow$$$ $$$f_i=1$$$ (even number of flips don't change the bit)
4. $$$k$$$ is odd, bit $$$i$$$ is $$$0$$$ $$$\Rightarrow$$$ $$$f_i=0$$$ (odd number of flips toggle the bit from $$$0$$$ to $$$1$$$)
Process the string from left to right until you can't anymore. If you still have some remaining moves at the end, you can just give them all to the last bit. Then you can construct the final string by checking the parity of $$$k-f_i$$$.
Time complexity: $$$\mathcal{O}(n)$$$