CF1439A2 Binary Table (Hard Version)

这是该问题的困难版本。不同之处在于可进行操作的次数不同。只有当你解决了两个版本的问题后，才可以进行 hack。 给你一个大小为 $n \times m$ 的二进制表格。该表格由 $0$ 和 $1$ 组成。 你可以进行如下操作：选择属于同一个 $2 \times 2$ 子方格的 $3$ 个不同单元格，并将这些单元格中的符号翻转（即 $0$ 变为 $1$，$1$ 变为 $0$）。 你的任务是将表格中的所有符号都变为 $0$。你最多可以进行 $nm$ 次操作。你不需要最小化操作次数。 可以证明，总是存在一种方案使得所有符号都变为 $0$。

第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。接下来的若干行描述每个测试用例。 每个测试用例的第一行包含两个整数 $n$、$m$（$2 \leq n, m \leq 100$）。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串，描述该表格的每一行。 保证所有测试用例的 $nm$ 之和不超过 $20000$。

对于每个测试用例，输出一个整数 $k$（$0 \leq k \leq nm$），表示操作次数。 接下来的 $k$ 行，每行输出 $6$ 个整数 $x_1, y_1, x_2, y_2, x_3, y_3$（$1 \leq x_1, x_2, x_3 \leq n, 1 \leq y_1, y_2, y_3 \leq m$），描述一次操作。该操作会对 $(x_1, y_1)$、$(x_2, y_2)$、$(x_3, y_3)$ 这三个不同的单元格进行。且这三个单元格都属于同一个 $2 \times 2$ 子方格。

在第一个测试用例中，可以只对 $(1, 1)$、$(2, 1)$、$(2, 2)$ 这三个单元格进行一次操作。操作后，所有符号都变为 $0$。 在第二个测试用例中： - 对 $(2, 1)$、$(3, 1)$、$(3, 2)$ 进行操作后，表格变为： ``` 011 001 000 ``` - 对 $(1, 2)$、$(1, 3)$、$(2, 3)$ 进行操作后，表格变为： ``` 000 000 000 ``` 在第五个测试用例中： - 对 $(1, 3)$、$(2, 2)$、$(2, 3)$ 进行操作后，表格变为： ``` 010 110 ``` - 对 $(1, 2)$、$(2, 1)$、$(2, 2)$ 进行操作后，表格变为： ``` 000 000 ``` 由 ChatGPT 4.1 翻译