题目描述

小挖做 Web 设计的时候，剧情里插入了酷炫的核填充情节！但很可惜，受制于技术，情节对应的游戏竟然是数独…

一开始，会给定你一个有 $n\times n$ 个宫，每个宫中有 $n \times n$ 个元素，且早已全部正确填好的 $n$ 阶数独。本题中数独游戏的详细表示与玩法见下方 “补充说明” 。

但小挖会把其中一些宫向左或者向右转 90 度/180 度。比如，若一个宫初始为

087
654
321

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

741
852
063

你在恢复数独时，也只能将一些宫向左转 90 度，一次旋转算作一步。现在小挖想考考你：如果把操作后的数独重新恢复成合法的数独，最少需要多少步呢？

如果一开始小挖给出的数独局面不可以通过任意次、任意位置的左旋得到，则输出 -1 。为什么呢？因为小挖给出的是“自认为完全正确的”数独，但实际不一定。

输入格式

第 $1$ 行，共一个整数 $n$ 。

第 $2\sim n^2+1$ 行，读入一个给定的数独局面，表示小挖操作之后的游戏。

输出格式

第 $1$ 行，表示最小步数 $s$。

第 $2\sim s+1$ 行，每行两个数 $x_i,y_i$。表示对行号列号为 $x_i,y_i$ 的宫向左旋转了 90 度。

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

设 $i

• $x_i\leq x_j$。

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

若不存在合法方案，请输出 -1 。

样例 #1

样例输入 #1

3
701210842
832478367
564653501
386648785
457235610
021170423
410702257
327514806
685368341

样例输出 #1

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

样例 #2

样例输入 #2

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

样例输出 #2

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$。

Hint

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

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