Rescue the Universe

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

The world is on the brink of collapse! Order has fallen into chaos.

We can abstract order as an n × n matrix containing a permutation of the numbers from 1 to n². You want to save the world, so you call upon a divine power. However, the deity’s power is limited – it can only swap two numbers if they are in the same row or in the same column. Moreover, the deity does not know which moves will restore order – it must follow your directions.

You do not need to achieve the restoration in the minimum number of swaps; you only need to ensure that the number of swaps you perform, k, does not exceed the worst‐case minimum number k₀ required for any permutation. In other words, if k is your number of swaps and k₀ is the maximum (over all 1 ≤  x  ≤  n²) of the minimal swap counts needed to restore order (using only same‐row or same‐column swaps), then you must have k ≤ k₀ for every input.

Note: The restoration means converting the matrix to the following form:

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

inputFormat

The first line contains an integer n (1 ≤ n ≤ 300), representing the dimensions of the matrix.

The next n lines each contain n space‐separated integers representing a permutation of 1, 2, …, n².

outputFormat

On the first line, output an integer k – the number of swaps.

Then output k lines, each containing four integers r₁ c₁ r₂ c₂, indicating that a swap is performed between the element in row r₁, column c₁ and the element in row r₂, column c₂. Rows and columns are 1-indexed.

Your solution must ensure that after performing all swaps, the matrix is in the required order, and the total number of swaps does not exceed the worst‐case minimum k₀ for any matrix.

sample

2
1 2
3 4

0