抽奖系列 · 第二关
子睿负责抽球，昊宇负责记录。一起找齐所有可能！

题目故事

元旦联欢会上，子睿和昊宇布置的“幸运抽奖角”热闹极了。这一次，他们想让抽奖箱里的小球数量也能发生变化。

子睿准备了 $n$ 个小球，分别写上编号 $1,2,ldots,n$，然后把它们放进抽奖箱。

每一轮，子睿从箱子里抽出一个小球，昊宇记下它的编号，接着子睿把这个小球放回箱中。连续进行 $n$ 轮，就得到一组包含 $n$ 个编号的抽奖记录。

“同一个球会不会连续出现呀？”子睿问。

“会呀！每次都放回去，每一轮都能抽到它。”昊宇翻开记录本，“我们把所有可能的记录都列出来，再按顺序排好吧！”

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

抽奖规则

同一个编号可以重复出现。抽取顺序不同，就属于不同的记录。例如，当 $n=3$ 时，1 2 3 和 3 2 1 是两种不同的情况。

输入格式

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

输出格式

按字典序从小到大输出全部抽奖记录，共 $n^n$ 行。

每行输出 $n$ 个整数，依次表示第 $1$ 次到第 $n$ 次抽到的小球编号。相邻两个整数之间用一个半角空格隔开，每种记录恰好输出一次。

仅输出这些记录，不要输出总数、提示文字或省略号。

样例 1

3

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

样例 1 说明

有 3 个小球，每次都有 3 种选择，共抽取 3 次，所以共有 $3^3=27$ 种记录。上面列出了全部 27 行，没有省略。

样例 2

2

1 1
1 2
2 1
2 2

样例 2 说明

有 2 个小球，共抽取 2 次，所以一共有 $2^2=4$ 种记录。1 1 和 2 2 都是允许出现的情况。

样例 3

1

1

什么是字典序？

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

例如，当 $n=3$ 时：

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

数据范围

本课堂改编版规定：对于所有测试数据，$1le nle 6$。