给你一个长度为 $$$n$$$ 的二进制字符串。您总共有 $$$k$$$ 步。在一次移动中,您必须选择一位。除该位外的所有位的状态都会翻转($$$0$$$ 变为 $$$1$$$,$$$1$$$ 变为 $$$0$$$)。您需要输出使用所有 $$$k$$$ 移动后可以获得的按字典顺序最大的字符串。另外,输出您将选择每个位的次数。如果有多种方法可以做到这一点,您可以输出其中任何一种。
二进制字符串 $$$a$$$ 按字典顺序大于相同长度的二进制字符串 $$$b$$$,当且仅当以下条件成立时:
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 包含 $$$1$$$,字符串 $$$b$$$ 包含 $$$0$$$。
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出两行。
第一行应包含您可以获得的按字典顺序排列的最大字符串。
第二行应包含 $$$n$$$ 整数 $$$f_1, f_2, \ldots, f_n$$$,其中 $$$f_i$$$ 是选择第 $$$i$$$ 位的次数。所有整数的总和必须等于 $$$k$$$。
示例
输入 #1
6 6 3 100001 6 4 100011 6 0 000000 6 1 111001 6 11 101100 6 12 001110
输出 #1
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
注意
这是第一个测试用例的解释。每个步骤都显示二进制字符串在移动过程中如何变化。
- 选择位$$$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}$$$。