题目描述

给定正整数 $n$，请按字典序从小到大输出 $1\sim n$ 的全部排列。

输入格式

一行一个整数 $n$。

输出格式

输出若干行，每行为一个排列，数字之间用一个空格隔开，按字典序升序。

输入输出样例 #1

输入 #1

3

输出 #1

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

说明

数据范围

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