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

The world is in peril! Order is in complete chaos.

Order can be abstracted as an $n \times n$ matrix containing a permutation of $1 \sim n^2$. You want to save the world, so you have summoned a god to help restore the order. However, the god is not omnipotent; it can only swap two numbers within the same row or the same column of the matrix. Furthermore, it does not know how to perform the swaps to restore the order and must follow your instructions.

Fortunately, you do not necessarily need to complete the restoration in the minimum number of swaps. You only need to ensure that your performance is no worse than the worst-case scenario. That is, if your number of swaps is $k$, and the maximum value of the minimum number of swaps across all permutations of $1 \sim n^2$ is $k_0$, you only need to satisfy $k \le k_0$.

Note: Restoration refers to 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

The first line contains a positive integer $n$.

The next $n$ lines each contain $n$ positive integers, representing the $n \times n$ matrix. It is guaranteed that each number from $1 \sim n^2$ appears exactly once.

Output

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

The next $k$ lines each contain four positive integers $x_1, y_1, x_2, y_2$, representing a swap between the number at row $x_1$, column $y_1$ and the number at row $x_2$, column $y_2$.

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

Examples

Input 1

2
4 2
3 1

Output 1

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

Note 1

It can be proven that this is one of the solutions with the minimum number of swaps, and it clearly satisfies the condition.

Input 2

2
2 1
3 4

Output 2

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

Note 2

For this input, the provided solution is not the one with the minimum number of swaps, but we know there exists a permutation of $1 \sim n^2$ (the previous example) that requires at least $3$ swaps, so this solution is valid.

Input 3

2
3 2
1 4

Output 3

2
1 1 1 1
1 1 2 1

Note 3

We allow the case where $(x_1, y_1) = (x_2, y_2)$.

Input 4

2
1 2
3 4

Output 4

0

Note 4

Note that $k$ can be $0$.

Subtasks

It is guaranteed that $1 \le n \le 1000$.

It is guaranteed that each number from $1 \sim n^2$ appears exactly once in the input matrix.