有一个 $n \times n$ 的棋盘，行和列标号都在 $[1,n]$ 内，现要在棋盘上放置 $n$ 个皇后使得它们不能相互攻击（即对于每个皇后，没有任何其他皇后和它处于同一行/列/对角线上）。

请按照字典序递增顺序输出所有解。

保证 $1 \le n \le 10$。

下江小春提醒您：长度为 $n$ 的字符串 $s_{1-n}$ 比长度为 $n$ 的字符串 $t_{1-n}$ 字典序更小，当且仅当存在下标 $k\in[1,n]$ 使得对于任意 $i\in[1,k),s_i=t_i$ 且 $s_k\lt t_k$。

输入方式

一个正整数 $n$ ，意义同上。

输出方式

输出若干行，每一行 $n$ 个正整数，这一行的第 $i$ 个正整数代表这一行所代表的方案中位于第 $i$ 行的皇后在这一行的哪一列（若该行没有皇后则输出 $0$）。

若此时无解，输出一行一个字符串：shikei!!! 来表示꒰ঌ(⸝⸝ ↀ ᯅ ↀ⸝⸝)໒꒱。

Samples

4

2 4 1 3
3 1 4 2