给你一个二进制(仅由 0 和 1 组成)$$$n \times m$$$ 矩阵。您还可以使用 XORificator,使用它可以反转所选行中的所有值(即将 0 替换为 1,将 1 替换为 0)。
矩阵中的一列如果恰好包含一个 1,则被视为特殊列。您的任务是找到可以同时变为特殊的最大列数,以及应使用 XORificator 的行集来实现此目的。
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$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$$$ 行上不使用异或器,则第 $$$i$$$ 字符为 0;如果在第 $$$i$$$ 行上使用异或器,则为 1。
如果有多个有效的 XORificator 配置可以实现最佳答案,则可以输出其中任何一个。
示例
输入 #1
5 3 4 1010 0110 0100 1 1 1 1 1 0 2 5 00101 10110 3 3 101 111 000
输出 #1
3 010 1 0 1 1 3 00 2 010
注意
在第一个测试用例中,您可以在第二行上使用 XORificator 使 $$$2$$$、$$$3$$$ 和 $$$4$$$ 列变得特殊。
在第二个测试用例中,唯一的列已经是特殊的,因此您不需要使用 XORificator。