CF1439A2.Binary Table (Hard Version)

This is the hard version of the problem. The difference between the versions is in the number of possible operations that can be made. You can make hacks if and only if you solved both versions of the problem.

You are given a binary table of size $n \times m$. This table consists of symbols $0$ and $1$.

You can make such operation: select $3$ different cells that belong to one $2 \times 2$ square and change the symbols in these cells (change $0$ to $1$ and $1$ to $0$).

Your task is to make all symbols in the table equal to $0$. You are allowed to make at most $nm$ operations. You don't need to minimize the number of operations.

It can be proved, that it is always possible.

这是该问题的困难版本。两个版本的区别在于可执行操作的数量。当且仅当你同时解决了该问题的两个版本时，你才可以进行 hack。

给你一个大小为 $n \times m$ 的二进制表格。该表格仅由符号 $0$ 和 $1$ 组成。

你可以执行如下操作：选择属于同一个 $2 \times 2$ 方格内的 三个不同单元格，并翻转这些单元格中的符号（即把 $0$ 变为 $1$，$1$ 变为 $0$）。

你的任务是使表格中所有符号都变为 $0$。你最多可以执行 $nm$ 次操作。你不需要最小化操作次数。

可以证明，该目标总是可达的。

The first line contains a single integer $t$ ($1 \leq t \leq 5000$) — the number of test cases. The next lines contain descriptions of test cases.

The first line of the description of each test case contains two integers $n$, $m$ ($2 \leq n, m \leq 100$).

Each of the next $n$ lines contains a binary string of length $m$, describing the symbols of the next row of the table.

It is guaranteed, that the sum of $nm$ for all test cases does not exceed $20000$.

第一行包含一个整数 $t$（$1 \leq t \leq 5000$），表示测试用例的数量。接下来的行包含各测试用例的描述。

每个测试用例描述的第一行包含两个整数 $n$、$m$（$2 \leq n, m \leq 100$）。

接下来的 $n$ 行，每行包含一个长度为 $m$ 的二进制字符串，用于描述表格下一行的符号。

保证所有测试用例的 $nm$ 之和不超过 $20000$。

For each test case print the integer $k$ ($0 \leq k \leq nm$) — the number of operations.

In the each of the next $k$ lines print $6$ integers $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$) describing the next operation. This operation will be made with three cells $(x_1, y_1)$, $(x_2, y_2)$, $(x_3, y_3)$. These three cells should be different. These three cells should belong to some $2 \times 2$ square.

对于每个测试用例，输出一个整数 $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$ 的正方形区域。

In the first test case, it is possible to make only one operation with cells $(1, 1)$, $(2, 1)$, $(2, 2)$. After that, all symbols will be equal to $0$.

In the second test case:

• operation with cells $(2, 1)$, $(3, 1)$, $(3, 2)$. After it the table will be:

  011
  001
  000

• operation with cells $(1, 2)$, $(1, 3)$, $(2, 3)$. After it the table will be:

  000
  000
  000

In the fifth test case:

• operation with cells $(1, 3)$, $(2, 2)$, $(2, 3)$. After it the table will be:

  010
  110

• operation with cells $(1, 2)$, $(2, 1)$, $(2, 2)$. After it the table will be:

  000
  000

在第一个测试用例中，只能对单元格 $(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