← 返回题目列表

Codeforces · 2081/C

C. 四元矩阵

中文机器翻译题面 查看原题

如果一个矩阵的所有元素都是 $$$0$$$、$$$1$$$、$$$2$$$ 或 $$$3$$$,则该矩阵称为四元矩阵。

Ecrade 调用四元矩阵 $$$A$$$ 好 如果以下两个属性成立。

  • 矩阵$$$A$$$每行中所有数字的按位异或等于$$$0$$$。
  • 矩阵$$$A$$$每列中所有数字的按位异或等于$$$0$$$。

Ecrade 有一个大小为 $$$n \times m$$$ 的四元矩阵。他感兴趣的是矩阵需要改变的最小数量 好,他还想找到可能的结果矩阵之一。

不过,好像有点困难,所以请帮助他!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 10^3$$$)。

接下来是 $$$n$$$ 行,每行恰好包含 $$$m$$$ 个字符,并且仅包含 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$,描述 Ecrade 矩阵的元素。

保证所有测试用例的 $$$n\cdot m$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例,打印矩阵需要更改的最小元素数 好 在第一行,然后打印 $$$n$$$ 行,每行恰好包含 $$$m$$$ 个字符,并且仅包含 $$$0$$$、$$$1$$$、$$$2$$$ 和 $$$3$$$,描述一个可能的结果矩阵。

如果有多个可能的结果矩阵,则输出其中任何一个。

示例

输入
复制

5
3 3
313
121
313
3 3
000
000
000
4 4
0123
1230
2301
3012
4 4
1232
2110
3122
1311
4 4
1232
2110
3122
1312

输出
复制

3
213
101
312
0
000
000
000
0
0123
1230
2301
3012
6
0132
2310
3131
1313
5
0132
2310
3120
1302