D. Одинаковое число единиц
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

ChthollyNotaSeniorious получил специальный подарок от AquaMoon: $$$n$$$ бинарных массивов длины $$$m$$$. AquaMoon говорит ему, что за одну операцию он может выбрать любые два массива и любую позицию $$$pos$$$ от $$$1$$$ до $$$m$$$ и поменять местами элементы на позициях $$$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$$$).

В $$$i$$$-й из следующих $$$n$$$ строк содержится $$$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)$$$  — минимальное необходимое количество операций.

$$$i$$$-я из следующих $$$k$$$ строк должна содержать $$$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}$$$: меняет местами $$$z_i$$$-е числа $$$x_i$$$-го и $$$y_i$$$-го массивов.

Пример
Входные данные
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
2 1 1
1
4 2 2
-1
Примечание

В первом наборе входных данных достаточно выполнить одну операцию: поменять местами первый элемент во второй и первой строках. Массивы станут $$$[0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]$$$, каждый из которых содержит ровно две $$$1$$$.