Problem Description

When Xiao Wa was doing Web design, the story included a cool nuclear refilling scene. But sadly, due to technical limits, the corresponding game turned out to be Sudoku...

At the beginning, you are given an already completely correctly filled $n$-order Sudoku. It has $n \times n$ blocks, and each block contains $n \times n$ elements. The detailed representation and rules of Sudoku in this problem are given in “Additional Notes” below.

However, Xiao Wa will rotate some blocks left or right by $90$ degrees / $180$ degrees. For example, if a block initially is

087
654
321

then after rotating it left by $90$ degrees, it becomes:

741
852
063

When you restore the Sudoku, you are also only allowed to rotate some blocks left by $90$ degrees. Each rotation counts as one step. Now Xiao Wa wants to test you: if you restore the operated Sudoku back into a valid Sudoku, what is the minimum number of steps needed?

If the Sudoku configuration given by Xiao Wa at the start cannot be obtained by any number of left rotations at any positions, output $-1$. Why? Because Xiao Wa thinks it is “completely correct”, but in fact it may not be.

Input Format

Line $1$ contains a positive integer $n$.

Lines $2$ to $n^2+1$ each contain $n^2$ hexadecimal integers, describing a given Sudoku configuration, which is the game state after Xiao Wa’s operations.

Output Format

Line $1$ outputs an integer, the minimum number of steps $s$.

Lines $2$ to $s+1$ each output two integers $x_i, y_i$, meaning you rotate the block at row index $x_i$ and column index $y_i$ left by $90$ degrees.

The testdata guarantees that when a solution exists, the optimal solution is unique. When outputting, please follow these rules:

Let $i<j$ mean the $i$-th and $j$-th steps in the output plan. Then:

• $x_i \le x_j$.
• If $x_i = x_j$, then $y_i \le y_j$.

If no valid plan exists, output $-1$.

3
701210842
832478367
564653501
386648785
457235610
021170423
410702257
327514806
685368341

12
1 1
1 1
1 2
1 3
2 1
2 2
2 3
2 3
3 1
3 1
3 3
3 3

4
36952EA1CF74857C
18E207C9B36D0419
4DAC56BF8209DFE2
B07FD3485AE1BA36
36B5B7CA6E5839FE
A4985620FD32A8B7
01CF94DF1B7C0564
7DE283E14A09C21D
B46D729D0F7246B0
8CF560154BCA159E
1327AB8459D8D278
EA09FC3E6E31A3CF
8E910623C5622B60
320BF7EDB847CDFE
45AF5A18310F183A
6CD7B9C4A9ED7459

17
1 1
1 1
1 2
1 2
1 3
1 3
1 4
2 2
2 3
2 4
3 1
3 2
3 2
3 3
4 1
4 2
4 4

Hint

For $40\%$ of the testdata, $2 \le n \le 3$.

For $100\%$ of the testdata, $2 \le n \le 4$.

Hint

The validity conditions for an $n$-order Sudoku: in every row, every column, and every thick-lined block $(n \times n)$, the numbers contain $0 \sim n^2-1$ with no repetition.

Note that in this problem’s representation for $4$-order Sudoku, numbers $>9$ are written in hexadecimal. More precisely, $\mathrm A = 10$, $\mathrm B = 11$, $\mathrm C = 12$, $\mathrm D = 13$, $\mathrm E = 14$, $\mathrm F = 15$.

Translated by ChatGPT 5