ChthollyNotaSeniorious 收到了来自 AquaMoon 的一份特殊礼物:$$$n$$$ 长度为 $$$m$$$ 的二进制数组。 AquaMoon 告诉他,在一次操作中,他可以选择从 $$$1$$$ 到 $$$m$$$ 的任意两个数组和任意位置 $$$pos$$$,并交换这些数组中位置 $$$pos$$$ 的元素。
他对这个游戏着迷,他想找到使所有数组中$$$1$$$的数量相同所需的最少运算次数。他邀请你来参加这个有趣的游戏,所以请尝试找到它!
如果可以,请按照输出部分描述的格式输出具体的交换步骤。否则,请输出$$$-1$$$。
输入
输入的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,如果目标无法实现,则输出 $$$-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$$$ 个数字。
示例
输入 #1
3 3 4 1 1 1 0 0 0 1 0 1 0 0 1 4 3 1 0 0 0 1 1 0 0 1 0 0 0 2 2 0 0 0 1
输出 #1
1 2 1 1 1 4 2 2 -1
注意
在第一个测试用例中,执行单个操作就足够了:交换第二行和第一行中的第一个元素。数组将变成$$$[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$$$,每个数组恰好包含两个$$$1$$$。