说明

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8 * 8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。

输入格式

一个整数n（ 1 < = n < = 10 )

输出格式

每行输出对应一种方案，每种方案顺序输出每一行皇后所在的列号，相邻两数之间用空格隔开，按字典序输出。如果不存在对应的方案，输出-1。

样例

4

2 4 1 3
3 1 4 2