Permutation Enumeration

与えらえた整数$n$に対して、$\{1, 2, ..., n\}$の全ての順列を辞書式順で順番に出力してください。

Input

１つの整数$n$が１行に与えられます。

Output

順列をそれぞれ1行に出力してください。数列の要素は空白で区切ってください。

Constraints

• $1 \leq n \leq 9$

Sample Input 1

2

Sample Output 1

1 2
2 1

Sample Input 2

3

Sample Output 2

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

---