D. XORофикатор
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана бинарная (состоящая из 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офикатора, вы можете вывести любую из них.

Пример
Входные данные
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
Примечание

В первом наборе входных данных можно применить XORофикатор ко второму ряду, тогда $$$2$$$-й, $$$3$$$-й и $$$4$$$-й столбцы будут особенными.

Во втором наборе входных данных единственный столбец уже особенный, поэтому применять XORофикатор не надо.