У Бурёнки есть две картины \(a\) и \(b\), представляющие собой таблицы одинакового размера \(n \times m\). Каждая клетка каждой картины имеет цвет — число от \(0\) до \(2 \cdot 10^5\), при этом ни в какой строке и никаком столбце каждой из двух картин нет повторяющихся цветов, за исключением цвета \(0\).
Бурёнка хочет получить из картины \(a\) картину \(b\). Для достижения своей цели Бурёнка может сделать одну из \(2\) операций: поменять местами две любые строки картины \(a\) или любые два её столбца. Сообщите Бурёнке, может ли она исполнить желаемое и если да, то подскажите ей последовательность действий.
Нумерация строк — от \(1\) до \(n\) сверху вниз, столбцов — от \(1\) до \(m\) слева направо.
Выходные данные
В первой строке выведите число \(-1\), если добиться желаемого невозможно, иначе выведите число действий в вашем решении \(k\) (\(0 \le k \le 2 \cdot 10^5\)). Можно доказать, что если решение существует, то существует решение, где \(k \le 2 \cdot 10^5\).
В следующих \(k\) строках выведите операции. Сначала выведите тип операции (\(1\) — поменять местами строки, \(2\) — столбцы), а потом два номера строк или столбцов, к которым применяется операция.
Обратите внимание, что вам не нужно минимизировать число операций.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 0 2
0 0 0
2 0 1
2 0 1
0 0 0
1 0 2
|
1
1 1 3
|
|
2
|
4 4
0 0 1 2
3 0 0 0
0 1 0 0
1 0 0 0
2 0 0 1
0 3 0 0
0 1 0 0
0 0 1 0
|
4
1 3 4
2 3 4
2 2 3
2 1 2
|
|
3
|
3 3
1 2 0
0 0 0
0 0 0
1 0 0
2 0 0
0 0 0
|
-1
|