输出自然数$1$到$n$所有不重复的排列，即$n$的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

输入格式

$n$

输出格式

由$1 \cdots n$组成的所有不重复的数字序列，每行一个序列。

样例

样例输入

3

样例输出

1  2  3
1  3  2
2  1  3
2  3  1
3  1  2
3  2  1

数据范围与提示

• 时间限制：$1000\mathrm{ms}$
• 空间限制：$512000\mathrm{KB}$
• $1 \leq n \leq 9$