ChthollyNotaSeniorious получил специальный подарок от AquaMoon: \(n\) бинарных массивов длины \(m\). AquaMoon говорит ему, что за одну операцию он может выбрать любые два массива и любую позицию \(pos\) от \(1\) до \(m\) и поменять местами элементы на позициях \(pos\) в этих массивах.
Его увлекла эта игра, и он хочет найти минимальное количество операций, которые необходимо выполнить, чтобы количество \(1\) во всех массивах было одинаковым. Он пригласил вас принять участие в этой интересной игре, поэтому, пожалуйста, попробуйте найти его!
Если это возможно, пожалуйста, выведите конкретные шаги обмена в формате, описанном в разделе выходных данных. В противном случае, пожалуйста, выведите \(-1\).
Выходные данные
Для каждого набора входных данных, если цель недостижима, выведите \(-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\)-го массивов.
Примечание
В первом наборе входных данных достаточно выполнить одну операцию: поменять местами первый элемент во второй и первой строках. Массивы станут \([0, 1, 1, 0], [1, 0, 1, 0], [1, 0, 0, 1]\), каждый из которых содержит ровно две \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
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
2 1 1
1
4 2 2
-1
|