该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

输出自然数 $1$ 到 $n$ 的所有排列，按照字典序从小到大输出，每个排列占一行。每个排列中的数字不能重复。

输入格式

一个整数 $n$。

限制

$1 ≤ n ≤ 9$

输出格式

输出所有 $1∼n$ 的全排列，每行一个排列，数字之间用空格隔开（若未特别说明，通常默认用空格隔开）。

样例

3

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