Вам дана бинарная (состоящая из 0 и 1) матрица размера $$$n \times m$$$. Также вам дан XORофикатор, который за одно применение умеет инвертировать все значения в выбранной строке (заменяет 0 на 1 и 1 на 0).
Будем называть столбец матрицы особенным, если в нём ровно одна 1. Вам надо найти максимальное количество столбцов, которые можно сделать особенными одновременно, и сказать, в каких строках нужно для этого применить XORофикатор.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 3 \cdot 10^5$$$, $$$n \cdot m \leq 3 \cdot 10^5$$$).
Каждая из следующих $$$n$$$ строк набора содержит бинарную строку длины $$$m$$$.
Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам входных данных не превышает $$$3 \cdot 10^5$$$.
Для каждого набора входных данных, выведите две строки.
В первой строке выведите максимальное количество особенных столбцов, которых можно получить одновременно.
Во второй строке выведите бинарную строку размера $$$n$$$, где на $$$i$$$-й позиции стоит 0, если XORофикатор на $$$i$$$-й строке применять не нужно, и 1, если XORофикатор на $$$i$$$-й строке применять нужно.
Если есть несколько подходящих конфигураций XORофикатора, вы можете вывести любую из них.
53 41010011001001 111 102 500101101103 3101111000
3 010 1 0 1 1 3 00 2 010
В первом наборе входных данных можно применить XORофикатор ко второму ряду, тогда $$$2$$$-й, $$$3$$$-й и $$$4$$$-й столбцы будут особенными.
Во втором наборе входных данных единственный столбец уже особенный, поэтому применять XORофикатор не надо.
| Codeforces Round 948 (Div. 2) |
|---|
| Закончено |
