最近小项的班级里流行一款推理谜题——星战（Star Battle）。它的规则如下：

       在一个行列的网格中，网格被划分成个不同的区域，你需要在网格上放置个星星，不过它们有一些限制。

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

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

从文件star.in中读入数据。

第一行一个数字。

接着行，每行个数字，表示第行第列的网格属于第个区域。

输出到文件star.out中。

如果谜题有解，则输出包含行，每行两个数字，第行表示第行的星星所在的行号和列号。如果没有解，输出-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)，能够使得行号小的星星列号尽可能小。

【样例3】

见选手目录下 star / star3.in和star / star3.ans。

【数据范围】

对于所有测试数据有：,保证每个区域在网格上是连续的。

 

 

附件：star1.ans 附件：star1.in 附件：star2.ans 附件：star2.in 附件：star3.ans 附件：star3.in