All permutations of given length

Input

One number $n$, 0 < n < 10.

Output

Print all permutations of numbers from $1$ to $n$ in lexicographical order. Print each permutation on a separate line. Do not print spaces between numbers on a line.

Examples