题目描述

给定一个整数 $n$，将数字 $1∼n$ 排成一排，将会有很多种排列方法。

现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行。

数据范围 $1\leq n\leq 9$

样例

3

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

提示

C++中有个专门做这个事情的函数。

来自acwing 823