Impressionism
Description
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.
Input
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$.
Output
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.
Samples
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