All Permutations

Interview

Time limit1sMemory limit256 MB

Summary

Print every permutation of the numbers 1 to N in lexicographic order, one per line.

Level: Easy3 of 10
Topics: Backtracking, Recursion
Solved: No attempts yet

Problem

Given $N$ , print every permutation of the numbers $1$ through $N$ in lexicographic order.

Input

The first line contains $N$ . ( $1 \le N \le 8$ )

Output

Starting from the first line, print all permutations in lexicographic order over $N!$ lines. Print one permutation per line, with a single space between numbers.

Examples1

Example 1
Input
```
3
```
Expected output
```
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
```