题目描述

对 1 ~ $n$ 进行全排列，并按字典序从小到大输出。

输入格式

只有一行，一个整数 $n$

输出格式

符合题目要求的输出，每种排列情况占一行。

样例数据

3

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

数据范围

对于 100% 的数据，$1 \le n \le 8$.