说明

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

N皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，输出所有不同的 N皇后问题 的解决方案。

每一种解法包含一个不同的 N皇后问题 的棋子放置方案。

请按照 从小到大顺序 输出。

如果不存在答案请输出 Error。

输入格式

一个整数 n

输出格式

所有可能的放置方案。

每行一个方案。

每行 n 个数字 a_i，表示将皇后放置在第 i 行的第 a_i 列上。

请按照 从小到大顺序 输出。

样例

4

2 4 1 3 
3 1 4 2 

提示

样例说明：

输入：n = 4

输出：[[2, 4, 1, 3],[3, 1, 4, 2]]

解释：如上图所示，4皇后问题存在两个不同的解法。

数据范围：

• 1 <= n <= 9