C. 四进制矩阵

题目翻译

如果一个矩阵中所有元素均为 $0$、$1$、$2$ 或 $3$，则称该矩阵为四进制矩阵。

如果一个四进制矩阵 $A$ 满足以下两个条件，则称其为完美矩阵：

1. 矩阵的每一行所有数字的按位异或和等于 $0$；
2. 矩阵的每一列所有数字的按位异或和等于 $0$。

Ecrade 有一个大小为 $n \times m$ 的四进制矩阵。 你需要解决两个问题：

1. 求出将该矩阵修改为完美矩阵所需的最少修改元素个数；
2. 构造出任意一个满足条件的最终矩阵。

输入格式

每个测试包含多组数据。 第一行输入一个整数 $t$（$1 \le t \le 2 \times 10^5$），表示测试用例数量。

每组测试用例：

• 第一行输入两个整数 $n, m$（$1 \le n,m \le 10^3$），表示矩阵的行数和列数；
• 接下来 $n$ 行，每行输入一个长度为 $m$ 的字符串，字符串仅由 $0,1,2,3$ 组成，表示原始矩阵。

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

输出格式

对于每组测试用例：

• 第一行输出一个整数，表示最少修改次数；
• 接下来 $n$ 行，每行输出一个长度为 $m$ 的字符串，表示修改后的完美矩阵（答案不唯一，输出任意合法矩阵即可）。

输入样例

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