Вам дана битовая строка длины \(n\). Вы должны сделать ровно \(k\) ходов. На каждом ходу вы должны выбрать один бит строки. Состояние всех битов кроме выбранного изменятся на противоположное (\(0\) станет \(1\), \(1\) станет \(0\)). Вам нужно вывести лексикографически максимальную строку, которую вы можете получить, используя все \(k\) ходов. Кроме того, для каждого бита выведите, сколько раз вы его выбираете для получения такой строки. Если есть несколько возможных решений, выведите любое из них.
Битовая строка \(a\) лексикографически больше битовой строки \(b\) такой же длины, если и только если выполняется следующее:
- в первой позиции, где \(a\) и \(b\) различны, в строке \(a\) находится \(1\), а в строке \(b\) — \(0\).
Выходные данные
Для каждого набора входных данных выведите две строки.
Первая строка должна содержать лексикографически максимальную строку, которую вы можете получить.
Вторая строка должна содержать \(n\) целых чисел \(f_1, f_2, \ldots, f_n\), где \(f_i\) — количество раз, которое вы выбираете \(i\)-й бит. Сумма всех чисел должна быть равна \(k\).
Примечание
Рассмотрим первый пример. Ниже пошагово показано, как изменяется строка после каждого хода.
- Выбирается бит \(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\), это лексикографически максимальная строка, которую можно получить.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|