All permutations of given length

Given number n. Print all permutations of numbers from 1 to n in lexicographical order.

Input

One number n (0 < n < 10).

Output

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

Examples