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

给你一个长度为 $n$ 的二进制字符串。你恰好有 $k$ 次操作。每次操作中，你必须选择某一位。除该位外，其余所有位的状态均被翻转（即 $0$ 变为 $1$，$1$ 变为 $0$）。你需要输出经过全部 $k$ 次操作后能得到的字典序最大的字符串，并输出每一位被选中的次数。若存在多种方案，输出任意一种即可。

当且仅当满足以下条件时，二进制字符串 $a$ 的字典序大于相同长度的二进制字符串 $b$：

• 在 $a$ 与 $b$ 首次出现差异的位置上，$a$ 中该位为 $1$，而 $b$ 中该位为 $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$.

第一行包含一个整数 $t$（$1 \le t \le 1000$）—— 表示测试用例的数量。

每个测试用例包含两行。第一行包含两个整数 $n$ 和 $k$（$1 \leq n \leq 2 \cdot 10^5$；$0 \leq k \leq 10^9$）。

第二行包含一个长度为 $n$ 的二进制字符串，其中每个字符为 $0$ 或 $1$。

所有测试用例的 $n$ 值之和不超过 $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$.

对于每个测试用例，输出两行。

第一行应包含你能得到的字典序最大的字符串。

第二行应包含 $n$ 个整数 $f_1, f_2, \ldots, f_n$，其中 $f_i$ 表示第 $i$ 位被选中的次数。所有整数之和必须等于 $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.

以下是第一个测试用例的解释。每一步都展示了二进制字符串在一次操作中如何变化。

• 选择第 $1$ 位：$\color{red}{\underline{1}00001} \rightarrow \color{red}{\underline{1}}\color{blue}{11110}$。
• 选择第 $4$ 位：$\color{red}{111\underline{1}10} \rightarrow \color{blue}{000}\color{red}{\underline{1}}\color{blue}{01}$。
• 选择第 $4$ 位：$\color{red}{000\underline{1}01} \rightarrow \color{blue}{111}\color{red}{\underline{1}}\color{blue}{10}$。

最终字符串为 $111110$，这也是我们能得到的字典序最大的字符串。