#P1718E. Impressionism

    ID: 7947 远端评测题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>constructive algorithmsgraphsimplementationmath

Impressionism

Description

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

Burenka wants to get a picture bb from the picture aa. To achieve her goal, Burenka can perform one of 22 operations: swap any two rows of aa 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 11 to nn from top to bottom, the columns are numbered from 11 to mm from left to right.

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

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

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

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

In the next kk lines print the operations. First print the type of the operation (11 — swap rows, 22 — 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 nn and mm (1nm21051 \leq n \cdot m \leq 2 \cdot 10^5) — the sizes of the table.

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

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

Output

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

In the next kk lines print the operations. First print the type of the operation (11 — swap rows, 22 — 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

样例输入 1

3 3
1 0 2
0 0 0
2 0 1
2 0 1
0 0 0
1 0 2

样例输出 1

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

样例输出 2

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

样例输出 3

-1