说明

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

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

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

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

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

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

输入格式

一个整数 $n$。

输出格式

所有可能的放置方案。 每行一个方案。 每行 $n$ 个数字 $a_i$，表示将皇后放置在第 i 行的第 $a_i$ 列上。 请按照 从小到大顺序 输出。

样例

4

2 4 1 3
3 1 4 2

提示

样例说明

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

数据范围

• $1 \le n \le 9$