Вам дана бинарная (состоящая из 0 и 1) матрица размера \(n \times m\). Также вам дан XORофикатор, который за одно применение умеет инвертировать все значения в выбранной строке (заменяет 0 на 1 и 1 на 0).
Будем называть столбец матрицы особенным, если в нём ровно одна 1. Вам надо найти максимальное количество столбцов, которые можно сделать особенными одновременно, и сказать, в каких строках нужно для этого применить XORофикатор.
Выходные данные
Для каждого набора входных данных, выведите две строки.
В первой строке выведите максимальное количество особенных столбцов, которых можно получить одновременно.
Во второй строке выведите бинарную строку размера \(n\), где на \(i\)-й позиции стоит 0, если XORофикатор на \(i\)-й строке применять не нужно, и 1, если XORофикатор на \(i\)-й строке применять нужно.
Если есть несколько подходящих конфигураций XORофикатора, вы можете вывести любую из них.
Примечание
В первом наборе входных данных можно применить XORофикатор ко второму ряду, тогда \(2\)-й, \(3\)-й и \(4\)-й столбцы будут особенными.
Во втором наборе входных данных единственный столбец уже особенный, поэтому применять XORофикатор не надо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 4
1010
0110
0100
1 1
1
1 1
0
2 5
00101
10110
3 3
101
111
000
|
3
010
1
0
1
1
3
00
2
010
|