最近小项的班级里流行一款推理谜题——星战（Star Battle）。它的规则如下： 在一个n行n列的网格中，网格被划分成n个不同的区域，你需要在网格上放置n个星星，不过它们有一些限制。

每个区域内只能放置一颗星星。
任意两个星星不能位于网格的同一行、同一列。
任意两个星星不能水平、垂直、对角线相邻。

小项是你的表弟，由于他把纸面的谜题变成程序的输入、以及把程序输出结果画在纸面上需要114.514秒，他希望你能开发一款程序，需要你的程序在1秒内得出星战谜题的解，并且先输出行号小的，后输出行号大的，如果有多组解，尽量使得前面行的星星的列号尽可能的小。你可以帮帮他吗？

从文件star.in中读入数据。第一行一个数字n。

接着n行，每行n个数字，a[i][j]表示第i行第j列的网格属于第a[i][j]个区域。

输出到文件star.out中。如果谜题有解，则输出包含n行，每行两个数字，第i行表示第i个区域的星星所在的行号和列号。如果没有解，输出-1即可。

【样例1解释】 谜面如下图，不同的区域用粗线分割开来：

谜面只有唯一解：1~5号区域的星星分别放置在(1,3) (2,5) (3,2) (4,4) (5,1)。

【样例2解释】 谜面如下图，不同的区域用粗线分割开来：

谜面有多组解，下面给出两种符合规则的解，但是只有上面那种解，(1,2)(2,6)(3,4)(4,7)(5,1)(6,3)(7,5)(8,8)，能够使得行号小的星星列号尽可能小。

对于所有测试数据有：1≤n≤15,1≤a[i][j]≤n,保证每个区域在网格上是连续的。

云南编程挑战赛