Permutations

Problem Background

Special for beginners, ^_^

Problem Description

Output all distinct permutations of the natural numbers $1$ to $n$, i.e. all permutations of $n$. In any produced sequence, no digit may be repeated.

Input Format

One natural number $n\;(1 \le n \le 9)$.

Output Format

All distinct sequences composed of the numbers $1\sim n$, one sequence per line, with the numbers separated by a single space.

Sample Input

3

Sample Output

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

Constraints

1s, 1024KiB for each test case.