CF1774D.Same Count One

ChthollyNotaSeniorious received a special gift from AquaMoon: $n$ binary arrays of length $m$. AquaMoon tells him that in one operation, he can choose any two arrays and any position $pos$ from $1$ to $m$, and swap the elements at positions $pos$ in these arrays.

He is fascinated with this game, and he wants to find the minimum number of operations needed to make the numbers of $1$s in all arrays the same. He has invited you to participate in this interesting game, so please try to find it!

If it is possible, please output specific exchange steps in the format described in the output section. Otherwise, please output $-1$.

ChthollyNotaSeniorious 收到了 AquaMoon 送来的特殊礼物：$n$ 个长度为 $m$ 的二进制数组。AquaMoon 告诉他，在一次操作中，他可以任选两个数组以及一个位置 $pos$（$1 \le pos \le m$），然后交换这两个数组在位置 $pos$ 处的元素。

他对这个游戏非常着迷，并希望找出使所有数组中 $1$ 的个数相等所需的最少操作次数。他邀请你一同参与这个有趣的游戏，请你尝试求解！

如果可行，请按输出部分所描述的格式输出具体的交换步骤；否则，请输出 $-1$。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 2\cdot 10^4$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($2 \leq n \leq 10^5$, $2 \leq m \leq 10^5$).

The $i$-th of the following $n$ lines contains $m$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$ $(0 \le a_{i, j} \le 1)$ — the elements of the $i$-th array.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 2\cdot 10^4$），表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 10^5$，$2 \leq m \leq 10^5$）。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$（$0 \le a_{i, j} \le 1$），表示第 $i$ 个数组的元素。

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

For each test case, if the objective is not achievable, output $-1$.

Otherwise, in the first line output $k$ $(0 \le k \le mn)$ — the minimum number of operations required.

The $i$-th of the following $k$ lines should contain $3$ integers, $x_i, y_i, z_i$ $(1 \le x_i, y_i \le n, 1 \le z_i \le m)$, which describe an operation that swap $a_{x_i, z_i}, a_{y_i, z_i}$: swap the $z_i$-th number of the $x_i$-th and $y_i$-th arrays.

对于每个测试用例，如果目标无法达成，则输出 $-1$。

否则，第一行输出 $k$ $(0 \le k \le mn)$ —— 所需的最少操作次数。

接下来的 $k$ 行中，第 $i$ 行应包含 $3$ 个整数 $x_i, y_i, z_i$ $(1 \le x_i, y_i \le n, 1 \le z_i \le m)$，描述一次操作：交换 $a_{x_i, z_i}$ 与 $a_{y_i, z_i}$，即交换第 $x_i$ 个数组和第 $y_i$ 个数组的第 $z_i$ 个数。

In the first test case, it's enough to do a single operation: to swap the first element in the second and the first rows. The arrays will become $[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$, each of them contains exactly two $1$s.

在第一个测试用例中，只需执行一次操作：交换第二行和第一行的第一个元素。数组将变为 $[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$，每个数组都恰好包含两个 $1$。