E. Импрессионизм
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Бурёнки есть две картины $$$a$$$ и $$$b$$$, представляющие собой таблицы одинакового размера $$$n \times m$$$. Каждая клетка каждой картины имеет цвет — число от $$$0$$$ до $$$2 \cdot 10^5$$$, при этом ни в какой строке и никаком столбце каждой из двух картин нет повторяющихся цветов, за исключением цвета $$$0$$$.

Бурёнка хочет получить из картины $$$a$$$ картину $$$b$$$. Для достижения своей цели Бурёнка может сделать одну из $$$2$$$ операций: поменять местами две любые строки картины $$$a$$$ или любые два её столбца. Сообщите Бурёнке, может ли она исполнить желаемое и если да, то подскажите ей последовательность действий.

Нумерация строк — от $$$1$$$ до $$$n$$$ сверху вниз, столбцов — от $$$1$$$ до $$$m$$$ слева направо.

Входные данные

В первой строке содержатся два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — размеры картин.

В $$$i$$$-й из следующих $$$n$$$ строк записаны $$$m$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$0 \leq a_{i,j} \leq 2 \cdot 10^5$$$) — цвета в $$$i$$$-й строке рисунка $$$a$$$. Гарантируется, что нет одинаковых чисел в одной строке или одном столбце, за исключением числа $$$0$$$.

В $$$i$$$-й из следующих $$$n$$$ строк записаны $$$m$$$ целых чисел $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}$$$ ($$$0 \leq b_{i,j} \leq 2 \cdot 10^5$$$) — цвета в $$$i$$$-й строке рисунка $$$b$$$. Гарантируется, что нет одинаковых чисел в одной строке или одном столбце, за исключением числа $$$0$$$.

Выходные данные

В первой строке выведите число $$$-1$$$, если добиться желаемого невозможно, иначе выведите число действий в вашем решении $$$k$$$ ($$$0 \le k \le 2 \cdot 10^5$$$). Можно доказать, что если решение существует, то существует решение, где $$$k \le 2 \cdot 10^5$$$.

В следующих $$$k$$$ строках выведите операции. Сначала выведите тип операции ($$$1$$$ — поменять местами строки, $$$2$$$ — столбцы), а потом два номера строк или столбцов, к которым применяется операция.

Обратите внимание, что вам не нужно минимизировать число операций.

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