Description

给出一个数 $N$ ，按照字典序从小到大输出 $1 - N$ 这 $N$ 个数的所有全排列。

Format

Input

第一行包含 $1$ 个正整数 $N$。

$1 \le N \le 8$ 。

Output

输出多行，每行 $N$ 个整数，应当为该 $N$ 个整数的一个全排列，$N$ 个数之间用空格隔开。

Samples

3

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