Lexicographical Permutations

Given an integer n, generate and output all unique permutations of the numbers from 1 to n in lexicographical order. Each permutation must contain each number exactly once. The permutations should be printed with the numbers separated by a single space and each permutation on a new line.

The mathematical representation of permutations of the set \(\{1, 2, \ldots, n\}\) can be described as all bijective functions from \(\{1,2,\ldots,n\}\) to itself.

inputFormat

The input consists of a single integer n (1 ≤ n ≤ 9).

outputFormat

Output all permutations of the numbers from 1 to n in lexicographical (dictionary) order. Each permutation should be printed on a new line with the numbers separated by a single space.

sample

1

1