题目描述

小婷有一条长度为 $n$ 的二进制灯带。一次操作选择一个位置，并翻转除此位置外的所有位。她必须恰好操作 $k$ 次，希望最终字符串字典序最大。

输入格式

第一行整数 $t$。每组数据第一行两个整数 $n,k$，第二行一个长度为 $n$ 的二进制字符串；所有组的 $n$ 之和不超过 $2\times10^5$。

输出格式

每组输出两行：第一行为最大字符串；第二行为 $n$ 个非负整数 $f_i$，表示每个位置被选择的次数，且总和必须为 $k$。答案不唯一时输出任意合法方案。

输入

1
50 621055027
00010011010011000001010001111111110100011001100111

输出

11111111111111111111111111111111111111111111111111
0 0 0 1 0 0 1 1 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 621055003

输入

1
52 553898774
0100110101011001001001111110111101111001000010111010

输出

1111111111111111111111111111111111111111111111111110
1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 0 553898752

输入

2
65 852555626
00101010110101000011101001100111100011000011110011101100110111100
31 754950011
0010010001011110011011100011111

输出

11111111111111111111111111111111111111111111111111111111111111110
1 1 0 1 0 1 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 0 0 1 852555596
1111111111111111111111111111111
0 0 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 0 0 0 1 1 1 1 754949995

数据范围

$1\le t\le1000$，$1\le n\le2\times10^5$，$0\le k\le10^9$。