Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

brute force

constructive algorithms

greedy

implementation

two pointers

*1600

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Same Count One

time limit per test

2 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputChthollyNotaSeniorious 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$$$.

Input

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$$$.

Output

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.

Example

Input

33 41 1 1 00 0 1 01 0 0 14 31 0 00 1 10 0 10 0 02 20 00 1

Output

1 2 1 1 1 4 2 2 -1

Note

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2023 14:24:40 (k3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|