You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个整数 n，输出 1~n 的所有全排列（按字典序）。

输入格式

一行一个整数 n（1 ≤ n ≤ 8）。

输出格式

若干行，每行一个排列，数字间空格隔开。

示例

输入：

3

输出

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