Code Submission Evaluation System Login

Datatähti Open 2018

Start:N/A
End:N/A
 

Tasks | Scoreboard | Statistics


CSES - Datatähti Open 2018 - SwapsCSES - Swaps

Swaps

Time limit:1.00 s
Memory limit:512 MB

There are two $n \times n$ grids, both of which contain the integers $1,2,\ldots,n^2$ in some order. The rows and columns of the grids are numbered $1,2,\ldots,n$.

There are two allowed operations:
  1. swap two chosen rows
  2. swap two chosen columns
Your task is to transform the first grid into the second grid using the operations, and also minimize the number of operations.

Input

The first input line contains an integer $n$: the size of the grids.

After this, there are $n$ lines that describe the first grid, and finally there are $n$ lines that describe the second grid.

Output

First print an integer $k$: the minimum number of operations. After this, print $k$ lines that describe the operations.

Each operation must be either of the form "$1$ $a$ $b$" (swap rows $a$ and $b$) or "$2$ $a$ $b$" (swap columns $a$ and $b$).

If there are no solutions, print only the value $-1$.

Example 1

Input:
3
1 2 3
4 5 6
7 8 9
2 1 3
8 7 9
5 4 6


Output:
2
2 1 2
1 2 3


Example 2

Input:
3
6 3 7
8 1 4
9 2 5
8 5 2
7 3 1
9 4 6


Output:
-1

Subtask 1 (12 points)
Subtask 2 (55 points)
Subtask 3 (33 points)