All Permutations

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

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

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.