抽奖系列 · 第三关
抽走的小球留在桌上，新的抽奖顺序等你发现！

题目故事

元旦联欢会还在继续，子睿和昊宇给“幸运抽奖角”换了一种玩法。

子睿准备了 $n$ 个小球，分别标上 1、2、…、$n$，一起放进抽奖箱。昊宇在旁边铺好记录纸，准备记下每次抽到的编号。

每次，子睿从箱中抽出一个小球。昊宇记录编号后，就把这个小球放到桌上的托盘里，不再放回箱中。连续抽取 $n$ 次后，箱子正好变空，记录纸上也留下了一组完整的抽奖顺序。

“如果第一个抽到 2 号球，第二个还能抽到 2 号球吗？”子睿问。

“不能啦，它已经在托盘里了！”昊宇笑着指了指记录纸，“不过，先抽谁、后抽谁，可有好多种可能呢。”

请你编写程序，帮他们找出所有可能的抽奖顺序，并按字典序从小到大输出。

抽奖规则

每组记录中，1 到 $n$ 的每个编号都恰好出现一次。顺序不同，就属于不同的情况，例如 1 2 3 和 3 2 1 是两种不同的抽奖顺序。

请枚举从箱中装有全部 $n$ 个小球的初始状态出发，所有可能的完整抽取顺序。

输入格式

输入一行，一个整数 $n$，表示小球的数量，同时也表示每组记录的抽取次数。

输出格式

按字典序从小到大输出所有可能的抽奖顺序，每种顺序恰好输出一次。

每种顺序占一行，包含 $n$ 个整数，依次表示第 1 次到第 $n$ 次抽到的小球编号。相邻两个整数之间用一个半角空格隔开。

仅输出抽奖顺序，不要输出总数、提示文字或省略号。

样例 1

3

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

样例 1 说明

第一次有 3 个小球可以选，第二次只剩 2 个，第三次只剩 1 个，所以共有 3 × 2 × 1 = 6 种顺序。上面的样例已经完整列出这 6 种情况。

样例 2

2

1 2
2 1

样例 2 说明

两个小球可以先抽 1 再抽 2，也可以先抽 2 再抽 1。由于小球不放回，1 1 和 2 2 都不合法。

样例 3

1

1

什么是字典序？

比较两组记录时，从左往右找到第一个不同的位置，该位置编号较小的记录排在前面。

例如，当 $n=3$ 时：

• 1 2 3 排在 1 3 2 前面，因为第 2 位首先不同，且 2 < 3。
• 1 3 2 排在 2 1 3 前面，因为第 1 位首先不同，且 1 < 2。

数据范围

对于所有测试数据，1 ≤ n ≤ 8。