题目描述

给定一个整数 $n$，请输出自然数 $1$ 到 $n$ 的所有全排列。

每个排列中，$1$ 到 $n$ 中的每个数字都恰好出现一次，不允许出现重复数字。

输入格式

输入一个整数 $n$。

输出格式

输出由 $1$ 到 $n$ 组成的所有全排列，每行输出一个排列。

每个数字占 $5$ 个字符宽度。

样例

3

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

数据范围

$1 \le n \le 9$。