Permutations

Input

One positive integer $n$ where 1 \le n \le 8 is given.

Output

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

Examples