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

问题描述

把 $1\sim n$ 的 $n$ 个正整数排成一行后随机打乱顺序，按字典序输出所有不同的方案。

输入格式

输入一行，包含一个正整数 $n$。$(1\le n\le 8)$

输出格式

输出 $n!$ 行，每一行为一种方案。字典序较小的先输出。

样例输入

3

样例输出

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