You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

相信你见过的很多数独问题都是要求把数独填充完整，但今天这个数独问题用到了另一个玩法……

题目描述

一开始，会给你一个早已全部填好的 $n$ 阶数独（有 $n\times n$ 个宫，每个宫中有 $n \times n$ 个元素）。该数独是把一个原始的正确数独经过若干次旋转操作得到的，此题中的旋转只允许把一个宫作为整体，向左旋转 90 度。例如，若一个宫初始为

087
654
321

那么它向左旋转 $90$ 度后会变成：

741
852
063

现在要求你恢复出原始的正确数独，恢复时也只能将一些宫向左转 $90$ 度，一次旋转算作一步。请问：把给你的数独恢复成原始的合法数独，最少需要多少步呢？

注意：数据保证当存在解时，最优解方案唯一。但由于出题人最近实在太忙，没时间认真检查所有数据，所以可能会存在原始数独是错误的情况，那么你只需要简简单单输出个 -1 即可。

本题中数独游戏的详细表示与玩法见下方 “补充说明” （就是正常数独的玩法，但以防我和你理解的“正常”有偏差，建议你还是读一读补充说明）。

输入格式

第 $1$ 行，输入一个正整数 $n$。

第 $2\sim n^2+1$ 行，每行输入 $n^2$ 个 $16$ 进制整数，表示一个给定的数独局面：把原始数独的一些宫旋转若干次后得到的数独。

输出格式

第 $1$ 行输出一个整数，表示最小步数 $s$。

第 $2\sim s+1$ 行，每行输出两个整数 $x_i,y_i$。表示对行号列号为 $x_i,y_i$ 的宫进行了一次旋转操作（向左旋转了 $90$ 度）。

数据保证当存在解时，最优解方案唯一。输出时请按如下规则输出：

设 $i<j$ 表示输出方案时的第 $i,j$ 两步。则：

• $x_i\leq x_j$
• 若 $x_i= x_j$ ，则 $y_i\leq y_j$

若不存在合法的恢复方案，请输出 -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

提示

对于 $40\%$ 的数据，$2 \le n\leq 3$。

对于 $100\%$ 的数据，$2 \le n\leq 4$。

补充说明

$n$ 阶数独合法的条件：每一行、每一列、每一个粗线宫 $(n\times n)$ 内的数字均含 $0\sim n^2-1$，且不重复。

需要注意的是，本题对于 $4$ 阶数独的表示方式中大于 $9$ 的数字采用了十六进制表示法。准确来说 $\mathrm A=10$，$\mathrm B=11$，$\mathrm C=12$，$\mathrm D=13$，$\mathrm E=14$，$\mathrm F=15$。