Problem Description

Some say it saved the world; others say it destroyed the world.

The world is in peril! Order has become chaotic.

Order can be abstracted into an $n \times n$ matrix, where the matrix contains a permutation of numbers from $1$ to $n^2$. You want to save the world, so you invite a deity to help restore order. However, the deity is not omnipotent; it can only swap two numbers within the same row or the same column. Moreover, it does not know how to swap to restore order and must follow your guidance.

Fortunately, you do not necessarily need to restore order in the minimum number of swaps. You only need to ensure that your number of swaps is not worse than the worst-case scenario. That is, if your number of swaps is $k$, and for all permutations of $1$ to $n^2$, the maximum value of the minimum number of swaps is $k_0$, you only need to satisfy $k \leq k_0$.

Note: Restoring order means transforming the matrix into the following form:

\[ \begin{matrix} 1 & 2 & 3 & \cdots & n \\ n+1 & n+2 & n+3 & \cdots & 2n \\ 2n+1 & 2n+2 & 2n+3 & \cdots & 3n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ (n-1)n+1 & (n-1)n+2 & (n-1)n+3 & \cdots & n^2 \end{matrix} \]

Input Format

The next $n$ lines, each containing $n$ positive integers, represent the $n \times n$ matrix. Each number from $1$ to $n^2$ appears exactly once.

Output Format

The first line contains a non-negative integer $k$, representing the number of swaps.

The next $k$ lines, each containing four positive integers $x_1, y_1, x_2, y_2$, indicate swapping the number at the $x_1$-th row and $y_1$-th column with the number at the $x_2$-th row and $y_2$-th column.

You must ensure that $x_1 = x_2$ or $y_1 = y_2$.

Sample Input and Output

Sample Input #1

2
4 2
3 1

Sample Output #1

3
1 1 1 2
1 2 2 2
1 1 1 2

Sample Input #2

2
2 1
3 4

Sample Output #2

3
2 1 2 2
1 1 1 2
2 1 2 2

Sample Input #3

2
3 2
1 4

Sample Output #3

2
1 1 1 1
1 1 2 1

Sample Input #4

2
1 2
3 4

Sample Output #4

0

Notes

• Sample 1 Explanation: This is one of the minimum swap solutions, clearly meeting the condition.
• Sample 2 Explanation: For this input, this output is not the minimum swap solution, but we know there exists a permutation (as in the previous example) that requires at least 3 swaps, so this solution is also valid.
• Sample 3 Explanation: We allow cases where $(x_1, y_1) = (x_2, y_2)$.
• Sample 4 Explanation: Note that $k$ can be equal to $0$.

Data Range and Constraints

• $1 \leq n \leq 1000$
• Each number from $1$ to $n^2$ appears exactly once in the input matrix.

见题面 Input 部分

见题面 Output 部分