B. Обращение битов
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана битовая строка длины $$$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$$$.

Пример
Входные данные
6
6 3
100001
6 4
100011
6 0
000000
6 1
111001
6 11
101100
6 12
001110
Выходные данные
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}$$$.
Итоговая строка равна $$$111110$$$, это лексикографически максимальная строка, которую можно получить.