题目描述

对一个如下的 8×8 的国际象棋棋盘，有八个皇后被放置在棋盘上，使得每行、每列和每条斜线上都至多只有一个皇后，这就是著名的八皇后问题，原图是其中一个解。

类似地我们可以定义 n 皇后问题：n×n 的国际象棋棋盘，有 n 个皇后被放置在棋盘上，使得每行、每列和每条斜线上都至多只有一个皇后。

你需要根据 n，输出 n 皇后问题的第一个解。容易发现一个解中，每行一定会恰好有一个皇后，我们规定两个解中如果前 k−1 行的皇后位置相同，则第 k 行的皇后更靠前（靠左）的排在前面。（或者说，以皇后的每行位置，按字典序排序）

输入格式

输入共 1 行：

第 1 行，一个正整数 n，表示我们要求解 n 皇后问题。（1≤n≤10）

输出格式

输出共 1 行：

第 1 行，n 个用空格隔开的正整数，依次表示第一组解中第 1、2、……、n 行的皇后在第几个位置。

8

1 5 8 6 3 7 2 4

1

1

2

数据范围与约定

1≤n≤10。