Permutations

Given a positive integer $n$, print all permutations of the integers from $1$ to $n$ in lexicographical order.

Input

One positive integer $n(1\le n\le 8)$.

Output

Print all permutations of the integers from $1$ to $n$ in lexicographical order. Print each permutation on a separate line.

Examples