小挖的核燃料填充

小挖做 Web 设计的时候，剧情里插入了酷炫的核填充情节！但很可惜，受制于技术，情节对应的游戏竟然是数独…… 一开始，会给定你一个有 $n\times n$ 个**宫**，每个宫中有 $n \times n$ 个元素，且**早已全部正确填好**的 $n$ 阶数独。本题中数独游戏的详细表示与玩法见下方 **“补充说明”** 。 但小挖会把其中**一些宫向左或者向右转 90 度/180 度**。比如，若一个宫初始为 ```cpp 087 654 321 ``` 那么它向左旋转 $90$ 度后会变成： ```cpp 741 852 063 ``` 你在恢复数独时，也**只能将一些宫向左转 $90$ 度**，一次旋转算作一步。现在小挖想考考你：如果把操作后的数独重新恢复成合法的数独，最少需要多少步呢？ 如果一开始小挖给出的数独局面不可以通过任意次、任意位置的左旋得到，则输出 $-1$ 。~~为什么呢？因为小挖给出的是“自认为完全正确的”数独，但实际不一定。~~ ## Input 第 $1$ 行，输入一个正整数 $n$。 第 $2\sim n^2+1$ 行，每行输入 $n^2$ 个 $16$ 进制整数，表示一个给定的数独局面，表示小挖操作之后的游戏。 ## Output 第 $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$。 [samples] ## Note 对于 $40\%$ 的数据，$2 \le n\leq 3$。 对于 $100\%$ 的数据，$2 \le n\leq 4$。 ## Hint $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$。