问题描述

把 $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