A15327 | Impressionism

Burenka has two pictures $a$ and $b$ , which are tables of the same size $n \times m$ . Each cell of each painting has a color — a number from $0$ to $2 \cdot 10^5$ , and there are no repeating colors in any row or column of each of the two paintings, except color $0$ .

Burenka wants to get a picture $b$ from the picture $a$ . To achieve her goal, Burenka can perform one of $2$ operations: swap any two rows of $a$ or any two of its columns. Tell Burenka if she can fulfill what she wants, and if so, tell her the sequence of actions.

The rows are numbered from $1$ to $n$ from top to bottom, the columns are numbered from $1$ to $m$ from left to right.

The first line contains two integers $n$ and $m$ ( $1 \leq n \cdot m \leq 2 \cdot 10^5$ ) — the sizes of the table.

The $i$ -th of the next $n$ lines contains $m$ integers $a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$ ( $0 \leq a_{i,j} \leq 2 \cdot 10^5$ ) — the colors of the $i$ -th row of picture $a$ . It is guaranteed that there are no identical colors in the same row or column, except color $0$ .

The $i$ -th of the following $n$ lines contains $m$ integers $b_{i, 1}, b_{i, 2}, \ldots, b_{i, m}$ ( $0 \leq b_{i,j} \leq 2 \cdot 10^5$ ) — the colors of the $i$ -th row of picture $b$ . It is guaranteed that there are no identical colors in the same row or column, except color $0$ .

In the first line print the number $-1$ if it is impossible to achieve what Burenka wants, otherwise print the number of actions in your solution $k$ ( $0 \le k \le 2 \cdot 10^5$ ). It can be proved that if a solution exists, then there exists a solution where $k \le 2 \cdot 10^5$ .

In the next $k$ lines print the operations. First print the type of the operation ( $1$ — swap rows, $2$ — columns), and then print the two indices of rows or columns to which the operation is applied.

Note that you don't have to minimize the number of operations.