题目描述

按字典序输出 $1$ 到 $n$ 的所有排列。

输入格式

一行一个整数 $n$。

输出格式

每行一个排列。

样例

3

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

数据规模与约定

$1\le n\le9$。