Generate All Permutations

You are given an array of n distinct integers. Your task is to generate and print all possible permutations of the array. The output should list each permutation on a separate line with each number separated by a single space. The permutations should be printed in lexicographical order (i.e. sorted in increasing order when considered as a sequence).

Recall that the total number of permutations of an array of n elements is given by \(n! = 1 \times 2 \times \cdots \times n\).

If the array is empty (i.e. n = 0), you should output a single empty line representing the one valid permutation: the empty permutation.

inputFormat

The input is read from stdin and consists of:

• An integer n (\(0 \leq n \leq 8\)), representing the number of elements in the array.
• If n > 0, then a line containing n space-separated integers follows. These are the distinct integers of the array.

outputFormat

Output to stdout all possible permutations of the array, one permutation per line. Each permutation should list its elements space separated. The permutations must be printed in lexicographical order. For the empty array (n = 0), output a single empty line.

## sample

3
1 2 3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

</p>